\(Update\:\:on\:\:2023.8.3\):增加了积性函数的内容,修改了内容排版
Part 1:欧拉函数及其性质
-
定义:欧拉函数 \(φ(n)\) 表示小于等于 \(n\),且与 \(n\) 互质的正整数的个数。
-
公式:
\[φ(n)=n*\dfrac{p_1-1}{p_1}*\dfrac{p_2-2}{p_2}*...*\dfrac{p_m-m}{p_m}=n*\prod\limits_{p\mid{n}}{(1-\dfrac{1}{p})}\qquad(p \in primes) \]
若在算数基本定理中,\(n=p_1^{c_1}p_2^{c_2}...p_m^{c_m}\)(\(p\) 为质数),则由容斥原理:关于此公式的证明,读者可自行推导
一些性质
-
若 \(n\) 是质数,则 \(φ(n)=n-1\)
-
若 \(n=p^k\),且 \(p\) 为质数,则 \(φ(n)=(p-1)*p^{k-1}\)
-
若 \(p\) 是质数,且 \(\begin{cases}p\mid{n}&\Rightarrowφ(nq)=φ(n)*q\\p\nmid{n}&\Rightarrowφ(nq)=φ(n)*(q-1)\end{cases}\)
-
\(n=\sum\limits_{d\mid{n}}{φ(d)}\)
-
\(φ(ab)=φ(a)*φ(b)*\frac{d}{φ(d)}\),其中 \(d=\gcd(a,b)\)
Part 2:积性函数
定义
若一个定义在正整数域上的函数 \(f\),当 \(x,y\) 互质时,有 \(f(xy)=f(x)*f(y)\),则称函数 \(f\) 是积性函数
特别地,当 \(x,y\) 不互质时仍有 \(f(xy)=f(x)*f(y)\) 的函数称为完全积性函数
常见完全积性函数:
- \(ϵ(n)=[n=1]\)
- \(I(n)=1\)
- \(id_k(n)=n^k\)
常见积性函数
- 欧拉函数 \(\varphi(n)\)
- 莫比乌斯函数 \(\mu=I^{-1}\)
- 除数函数 \(\sigma_k(n)=\sum\limits_{d\mid n}d^k\)
- 除数函数 \(d(n)=\) \(n\) 的约数个数
- \(s(n)=n\) 所有约数的和
一些乘积结论
-
\(\mu(ij)=[i\perp j]\mu(i)\mu(j)\)
-
\(φ(ab)=φ(a)*φ(b)*\frac{d}{φ(\gcd(a,b))}\)
-
\(d(ij)=\sum\limits_{x|i}\sum\limits_{y|j}[x\perp y]\)
-
\(\sigma_k(ij)=\sum\limits_{x|i}\sum\limits_{y|j}[x\perp y](\frac{xj}{y})^k\)
除数函数的计算
对于 \(n=p_1^{c_1}p_2^{c_2}\dots p_m^{c_m}\),有:
-
\(d(n)=(c_1+1)(c_2+1)\dots(c_m+1)\)
记 \(p\) 为 \(n\) 的最小质因子,有:
\[d(n)=\begin{cases}2d(n/p)-d(n/p^2)&p^2\mid n\\2d(n/p)&\rm otherwise\end{cases} \] -
\(\sigma_k(n)=\prod\limits_{i=1}^m(1+p_i+p_i^2+\dots+p_i^{c_i})\)
Part 3:欧拉函数例题
【模板题】求 φ(n)
解题思路
- 我们已知 \(φ(n)\) 的计算公式,所以只需对 \(n\) 进行质因数分解即可
代码
#include<bits/stdc++.h>
using namespace std;
const int N=100001;
int n;
int GetPhi(int n)
{
int ans=n;
for(int i=2; i*i<=n; i++) //分解质因数
{
if(n%i==0)
{
ans=ans*(i-1)/i; //计算公式
while(n%i==0)
n/=i;
}
}
if(n>1) //还剩下一个较大的质数
ans=ans*(n-1)/n;
return ans;
}
int main()
{
cin>>n;
cout<<GetPhi(n);
return 0;
}
【模板题】求 φ(1) ~ φ(n)
解题思路
-
由于欧拉函数是积性函数,所以我们考虑用线性筛求解
-
从欧拉函数性质 \(3\) 出发,在线性筛中,每个合数 \(x\) 都会被它最小的质因子 \(p\) 筛去,此时我们就可以用 \(p\) \((\)或 \(p-1)\) 和 \(φ(x/p)\) 来推出 \(φ(x)\) ,具体是 \(p\) 还是 \(p-1\),要看 \(x/p\),即我们外层循环的 \(i\) 是否是 \(q\) 的倍数;而对于每个质数 \(y\),由性质 \(1\) 可得:\(φ(y)=y-1\)
代码
#include<bits/stdc++.h>
using namespace std;
const int N=100001;
int n,phi[N],v[N],prime[N],tot;
void GetPhi(int n)
{
phi[1]=1;
for(int i=2; i<=n; i++)
{
if(!v[i])
{
v[i]=i;
prime[++tot]=i;
phi[i]=i-1;
}
for(int j=1; j<=tot; j++)
{
if(prime[j]>v[i] || prime[j]>n/i)
break;
v[i*prime[j]]=prime[j];
if(i%prime[j]==0)
phi[i*prime[j]]=prime[j]*phi[i];
else
phi[i*prime[j]]=(prime[j]-1)*phi[i];
}
}
}
int main()
{
cin>>n;
GetPhi(n);
for(int i=1; i<=n; i++)
cout<<phi[i]<<" ";
return 0;
}
【练习题】公约数的和
(题目传送门)
题目大意
给定 \(n\),求
\[\sum\limits_{i = 1}^n \sum\limits_{j = i + 1}^n \gcd(i, j) \]其中 \(\gcd(i, j)\) 表示 \(i\) 和 \(j\) 的最大公约数。
解题思路
-
我们记 \(ans=\sum\limits_{i = 1}^n \sum\limits_{j = i + 1}^n \gcd(i, j)\)
-
改写一下可得:
\[ans=\dfrac{\sum\limits_{i = 1}^n \sum\limits_{j =1}^n \gcd(i, j)-\sum\limits_{i=1}^n\gcd(i,i)}{2} \]\[=\dfrac{\sum\limits_{i = 1}^n \sum\limits_{j =1}^n \gcd(i, j)-\sum\limits_{i=1}^ni}{2} \] -
那么我们枚举最大公约数 \(d\),设 \(f(d)\) 表示有多少对 \((i,j)\) 使得 \(\gcd(i,j)=d\),那么就有
\[ans=\dfrac{\sum\limits_{d=1}^n{d*f(d)} -\sum\limits_{i=1}^ni}{2} \] -
进一步思考,若整数对 \((i,j)\) 满足 \(\gcd(i,j)=d\),则有:\(i\mid d,\: j\mid d,\:\gcd(i/d,j/d)=1\)。
-
设 \(x=i/d,\:y=j/d\),下面分 \(3\) 种情况讨论对于每一个 \(x\),有多少个 \(y\) 满足 \(\gcd(x,y)=1\):
1、若 \(i>j\),则 \(x>y\)。又因为 \(j<i \leqslant n\),所以 \(y<x \leqslant n/d\)。那么满足 \(\gcd(x,y)=1\) 的 \(y\) 的数量就为 \(1\) ~ \(x\) 里与 \(x\) 互质的数的个数,即 \(φ(x)\)。
2、若 \(i<j\),则 \(x<y\),那么令 \(x'=y,\:y'=x\),那么此时的答案即为第 1 种情况中已求出的满足 \(\gcd(x',y')=1\) 的 \(y\) 的数量。所以答案为 \(φ(x')\)。因此,每一个 \(φ(x)\) 都会被算 \(2\) 遍
3、若 \(i=j\),则 \(x=y\),此时 \(y\) 的取值很明显只有 \(1\) 种
-
综上,
\[f(d)=(\sum\limits_x^{n/d}{φ(x)})*2+1 \] -
在求 \(f(d)\) 前,可对 \(φ()\) 进行前缀和的预处理,节省时间
代码
#include<bits/stdc++.h>
using namespace std;
const int N=2000010;
int n,phi[N],v[N],prime[N],tot;
long long ans,sum[N],f[N];
void GetPhi(int n) //求phi[1~n]
{
phi[1]=1;
for(int i=2; i<=n; i++)
{
if(!v[i])
{
v[i]=i;
prime[++tot]=i;
phi[i]=i-1;
}
for(int j=1; j<=tot; j++)
{
if(prime[j]>v[i] || prime[j]>n/i)
break;
v[i*prime[j]]=prime[j];
if(i%prime[j]==0)
phi[i*prime[j]]=prime[j]*phi[i];
else
phi[i*prime[j]]=(prime[j]-1)*phi[i];
}
}
for(int i=1; i<=n; i++) //前缀和预处理
sum[i]=sum[i-1]+(long long)phi[i];
}
int main()
{
cin>>n;
GetPhi(n);
for(int i=1; i<=n; i++)
f[i]=sum[n/i]*2-1,ans+=f[i]*(long long)i; //求f和ans
ans=(ans-(long long)(1+n)*n/2)/2; //最后一步
cout<<ans;
return 0;
}
【练习题】GCD(x,n)>=m
题目大意
给定整数 \(n\) 和 \(m\),问题是求有多少个整数 \(x\),满足 \(1 \leqslant x \leqslant n\) 且 \(\gcd(x,n) \geqslant m\)。
解题思路
-
记 \(\gcd(x,n)=d\),那么由定义得:\(d \mid n\) 。因此我们考虑去枚举 \(n\) 的约数,并舍去其中小于 \(m\) 的约数,那么剩下的数便可以作为 \(d\) 的取值。
-
对于大于等于 \(m\) 的约数 \(i\),由上一题的解题思路可知:\(x\mid i\) 且 \(\gcd(x/i,n/i)=1\),所以答案便为 \(φ(n/i)\)
代码
#include<bits/stdc++.h>
#define LL long long
using namespace std;
int T,n,m;
LL ans;
LL GetPhi(int n) //求phi[n]
{
LL ans=(LL)n;
for(int i=2; i*i<=n; i++)
{
if(n%i==0)
{
ans=ans*(LL)(i-1)/i;
while(n%i==0)
n/=i;
}
}
if(n>1)
ans=ans*(LL)(n-1)/n;
return ans;
}
int main()
{
scanf("%d",&T);
while(T--)
{
scanf("%d%d",&n,&m);
ans=0;
for(int i=1; i*i<=n; i++) //枚举约数
{
if(n%i==0)
{
if(i>=m) //约数i
ans=ans+(LL)GetPhi(n/i);
if(i!=n/i && n/i>=m) //由于约数成对出现,所以n/i也是n的约数,注意要避免完全平方数的情况
ans=ans+(LL)GetPhi(i);
}
}
printf("%lld\n",ans);
}
return 0;
}
【练习题】非互质数求和
题目大意
如果一个正整数 \(x\) 小于 \(n\),而且 \(x\) 与 \(n\) 不互质,那么整数 \(x\) 称为“好数”。
给定一个正整数 \(n\),求所有的“好数”的和。
这里互质的定义:如果 \(A,B\) 除 \(1\) 外没有其他的公因数,则称 \(A\) 与 \(B\) 互质。
答案模 \(1000000007\)。
解题思路
-
考虑到正面求解较难,我们可以考虑求答案的补集,即求所有与 \(n\) 互质的数的和
-
在这我们先引入一个结论:
\[\gcd(n,x)=\gcd(n,n-x) \]这个结论我们最后会来证明。
那么如果 \(x\) 与 \(n\) 互质,由结论就可知 \(n-x\) 也与 \(n\) 互质
-
设集合 \(X\) 为与 \(n\) 互质的数的集合。则集合元素个数为 \(φ(n)\),集合元素分别为 \(x_1,x_2\:......\:x_{φ(n)}\)。由刚刚的结论可知 \(x_i+x_{φ(n)-i+1}=n\),这样的数对共有 \(φ(n)/2\) 个,所以 \(\sum\limits_{i=1}^{φ(n)}{x_i}=\dfrac{n*φ(n)}{2}\)
-
最后答案即为 \(\sum\limits_{i=1}^{n-1}{i}-\dfrac{n*φ(n)}{2}\)
关于引入结论的证明
-
设 \(d=\gcd(n,x)\),则有 \(n=k_1d,\:x=k_2d\) 且 \(\gcd(k_1,k_2)=1 \quad (k_1,k_2 \in \mathbb{N^*})\),那么 \(n-x=(k_1-k_2)d\)
-
假设 \(\gcd(n,n-x) \ne d\),则 \(\gcd(k_1,k_1-k_2) \ne 1\)。所以可设 \(k_1=ab,k_1-k_2=ac\ (a\ne 1,\quad a,b,c \in \mathbb{N^*})\),那么可推出 \(k_2=a(b-c)\),易知 \(b-c \ne 0\),所以 \(\gcd(k_1,k_2) \ne 1\),因此假设矛盾
-
综上,\(\gcd(n,x)=\gcd(n,n-x)\)
代码
#include<bits/stdc++.h>
using namespace std;
const long long MOD=1000000007;
long long n;
long long GetPhi(long long m) //求phi[n]
{
long long ans=m;
for(int i=2; i*i<=m; i++)
{
if(m%i==0)
{
ans=ans*(i-1)/i;
while(m%i==0)
m/=i;
}
}
if(m>1)
ans=ans*(m-1)/m;
return ans;
}
int main()
{
while(scanf("%lld",&n))
{
if(n==0)
break;
printf("%lld\n",(n*(n-1)/2-n*GetPhi(n)/2)%MOD);
}
return 0;
}
【练习题】USB的数学题
题目大意
求 \(F(n)=\sum\limits_{i=1}^n{\dfrac{n}{\gcd(i,n)}}\) 的值
\(T\) 组测试数据(\(T,n \leqslant 10^7\))
解题思路
-
设 \(d=\gcd(i,n)\),则满足 \(\gcd(i,n)=d\) 的 \(i\) 的个数就为 \(φ(n/d)\)。所以 \(F(n)\) 可写成
\[F(n)=\sum\limits_{d\mid n}^{}{φ(d)*d} \] -
再看一眼数据范围,显然对于每组测试数据的每个 \(n\),都进行根号级别的枚举是无法拿到满分的,所以我们要思考 \(F(n)\) 所具有的其它性质——没错,积性函数!
-
\(F\) 是积性函数是很好证明的。设 \(x,y\) 为互质的两个正整数。则 \(F(x)=\sum\limits_{a\mid x}^{}{(φ(a)*a)},\:F(y)=\sum\limits_{b\mid y}^{}{(φ(b)*b)}\)。那么 \(F(x)*F(y)=\sum\limits_{a\mid x}^{}{(φ(a)*a)}*\sum\limits_{b\mid y}^{}{(φ(b)*b)}\:\)。由于 \(x\) 与 \(y\) 互质,所以 \(a\) 与 \(b\) 也是互质的,再加上 \(φ\) 是积性函数,所以
\[F(x)*F(y)=\sum\limits_{ab\mid xy}^{}{φ(ab)*ab}=F(xy) \]因此,\(F\) 是积性函数
-
一开始我们已经说过,所有的积性函数都可以用线性筛求解。本题我们分 \(3\) 种情况对 \(F\) 的递推进行讨论:
1、当 \(n=10\) 时,\(10\) 的最小质因子为 \(2\),\(2\) 与 \(10/2=5\) 互质,所以 \(F(10)\) 可以由 \(F(2)*F(5)\) 得到。这是最简单的一种情况。
2、当 \(n=12\) 时,\(12\) 的最小质因子为 \(2\),但 \(2\) 与 \(12/2=6\) 不互质,所以此时无法直接递推。因为 \(12=2^2*3\),所以我们需要令 \(a=2^2,\:b=3\),这样 \(a\) 与 \(b\) 一定是互质的,再通过 \(F(a)*F(b)\) 得到 \(F(12)\)。因此,我们需要记录每一个数的最小质因子的最高次幂的值,记为 \(highPow[n]\)。对于这种情况,我们就可以令 \(a=highPow[n],b=n/a\),再通过 \(F(a)*F(b)\) 得到 \(F(n)\)
3、当 \(n=8\) 时,\(a=highPow[8]=8,\:b=8/a=1\),就会产生 \(F(8)=F(8)*F(1)\) 这样的情况,所以我们还需要记录 \(n\) 的最小质因子的指数,记为 \(mi[n]\)。那么当 \(n=x^{mi[n]}\) 时,我们可以暴力求解 \(F(n)=\sum\limits_{d\mid n}^{}{φ(d)*d}\:\)。显然我们有 \(F(n)=\sum\limits_{i=1}^{mi[n]}{x^i*φ(x^i)}+1\:\) (\(+1\)是当 \(d=1\) 的情况)。由 \(φ\) 的计算公式,我们就可以得到:
\[F(n)=\sum\limits_{i=1}^{mi[i]}{x^i*x^i*(1-\dfrac{1}{x})}+1 \]\[=\sum\limits_{i=1}^{mi[i]}{x^i*x^i*(\dfrac{x-1}{x})}+1 \]\[=\sum\limits_{i=1}^{mi[i]}{x^i*x^{i-1}*(x-1)}+1 \]我们再通过一个简单的前缀积处理,就可以暴力的求解这种情况的 \(F(n)\)
代码
#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int N=10000010;
int T,n;
int v[N],prime[N],tot;
LL f[N],highPow[N],mi[N],tmp[N];
void prework(int n)
{
f[1]=1;
for(int i=2; i<=n; i++)
{
if(!v[i])
{
v[i]=i;
prime[++tot]=i;
f[i]=(LL)(i-1)*i+1;
highPow[i]=i;
mi[i]=1;
}
for(int j=1; j<=tot; j++)
{
if(prime[j]>v[i] || prime[j]>n/i)
break;
int x=i*prime[j];
v[x]=prime[j];
if(i%prime[j]!=0) //第1种情况(由于prime[j]是质数,所以i与prime[j]互质当且仅当i不是prime[j]的倍数或约数)
{
highPow[x]=prime[j];
mi[x]=1;
f[x]=f[i]*f[prime[j]];
}
else
{
highPow[x]=highPow[i]*prime[j];
mi[x]=mi[i]+1;
int a=highPow[x],b=x/a;
if(b==1) //第3种情况
{
tmp[0]=1;
for(int i=1; i<=mi[x]; i++)
tmp[i]=tmp[i-1]*(LL)prime[j]; //前缀积处理prime[j]的幂
for(int i=1; i<=mi[x]; i++)
f[x]+=tmp[i]*tmp[i-1]*(LL)(prime[j]-1); //暴力求解
f[x]++; //加上d=1的情况
}
else //第2种情况
f[x]=f[a]*f[b];
}
}
}
}
int main()
{
prework(N-10);
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
printf("%lld\n",f[n]);
}
return 0;
}
标签:prime,函数,limits,积性,sum,int,ans,欧拉,gcd
From: https://www.cnblogs.com/xishanmeigao/p/17610169.html