数论函数
定义域为整数,值域为复数的函数
积性函数:若 ,则
除数函数
除数函数为积性函数。
欧拉函数 
表示不超过
且与
互质的正整数的个数
其中 是
的标准分解。
由此易见 函数是积性函数。
同时满足
线性求 函数:
#define int long long int phi[3000005]; int n=3000000; bool mark[3000005]; int prime[1000005]; int tot; void getphi() { phi[1]=1; for(int i=2;i<=n;i++) { if(mark[i]==false) { prime[++tot]=i; phi[i]=i-1; } for(int j=1;j<=tot;j++) { if(i*prime[j]>n) { break; } mark[i*prime[j]]=true; if(i%prime[j]==0) { phi[i*prime[j]]=phi[i]*prime[j]; break; } phi[i*prime[j]]=phi[i]*phi[prime[j]]; } } for(int i=1;i<=n;i++) { phi[i]+=phi[i-1]; } }
函数 &preview=true)
证明:
$$
其中 即
设
那么
根据二项式定理,易知该式子的值在 即
时值为
否则为
,这也同时证明了
#define int long long int mu[3000005]; int n=3000000; bool mark[3000005]; int prime[1000005]; int tot; void getmu() { mu[1]=1; for(int i=2;i<=n;i++) { if(mark[i]==false) { prime[++tot]=i; mu[i]=-1; } for(int j=1;j<=tot;j++) { if(i*prime[j]>n) { break; } mark[i*prime[j]]=true; if(i%prime[j]==0) { mu[i*prime[j]]=0; break; } mu[i*prime[j]]=-mu[i]; } } }
卷积
定义两个数论函数的卷积为:
$\text{Dirichlet}
\varepsilon
\varepsilon(n)=[n==1]
\varepsilon
1*\mu=\varepsilon
\mu * \text{ID} = \varphi
1*\text{ID}=\sigma$
莫比乌斯反演
公式:设 为两个数论函数。
如果有
$f=g*1
g=f*\mu
f\mu=g1\mu= g\varepsilon=g
1*\mu=\varepsilon$ )
同时,还有另一种反演:
如果有
$$
整除分块
当遇到形如
$O(\sqrt {n})
i
\frac{n}{i}
\frac{n}{i}
x
x
\frac{n}{x}$。
- 证明:反证法:对于数
,它所在的块的值为
,且
。
数
和数
不在同一个块中。
然后,原命题得证。
所以,易得计算原式方法。
for(int l=1,r;l<=n;l=r+1) { r=n/(n/l); ans+=(r-l+1)*(n/l); }
P2257 YY的GCD
设,
由莫比乌斯反演:
改为枚举:
设
代码:
//sum即为的前缀和
#include<bits/stdc++.h> using namespace std; #define ll long long int prime[10000005]; int mu[10000005]; ll f[10000005]; ll sum[10000005]; bool vis[10000005]; int cnt; void init() { mu[1]=1; for(int i=2;i<=10000000;i++) { if(vis[i]==false) { mu[i]=-1; prime[++cnt]=i; } for(int j=1;j<=cnt&&i*prime[j]<=10000000;j++) { vis[i*prime[j]]=true; if(i%prime[j]==0) { break; } mu[i*prime[j]]=-mu[i]; } } for(int i=1;i<=cnt;i++) { for(int j=1;j*prime[i]<=10000000;j++) { f[j*prime[i]]+=mu[j]; } } for(int i=1;i<=10000000;i++) { sum[i]=sum[i-1]+f[i]; } } ll solve(int a,int b)//运用整除分块 { ll ans=0; if(a>b) { swap(a,b); } for(int l=1,r=0;l<=a;l=r+1) { r=min(a/(a/l),b/(b/l)); ans+=(ll)(sum[r]-sum[l-1])*(a/l)*(b/l); } return ans; } signed main() { init(); int T; cin>>T; for(int i=1;i<=T;i++) { int a,b; scanf("%d %d",&a,&b); printf("%lld\n",solve(a,b)); } return 0; }
常用柿子
$$
调和数
杜教筛
快速求出
由于
可得
右边为子问题,可以递归解决,再加整除分块,可以保证每个点被计算一遍
复杂度
代码:
#include<bits/stdc++.h> using namespace std; #define re register #define ll long long #define N 5500000 ll phi[N+5]; int mu[N+5]; int prim[N+5]; bool mark[N+5]; int cnt; unordered_map<int,ll> aphi; unordered_map<int,int> amu; void init() { phi[1]=1; mu[1]=1; for(re int i=2;i<=N;i++) { if(mark[i]==false) { phi[i]=i-1; mu[i]=-1; prim[++cnt]=i; } for(re int j=1;j<=cnt;j++) { if(i*prim[j]>N) { break; } mark[i*prim[j]]=true; if(i%prim[j]==0) { phi[i*prim[j]]=phi[i]*prim[j]; mu[i*prim[j]]=0; break; } phi[i*prim[j]]=phi[i]*phi[prim[j]]; mu[i*prim[j]]=-mu[i]; } } for(re int i=1;i<=N;i++) { phi[i]+=phi[i-1]; mu[i]+=mu[i-1]; } } ll getphi(int x) { if(x<=N) { return phi[x]; } if(aphi[x]!=0) { return aphi[x]; } ll ans=(ll)x*(x+1)/2; for(int l=2,r=0;r!=2147483647&&l<=x;l=r+1) { r=x/(x/l); ans-=(ll)(r-l+1)*getphi(x/l); } return aphi[x]=ans; } int getmu(int x) { if(x<=N) { return mu[x]; } if(amu[x]!=0) { return amu[x]; } int ans=1; for(int l=2,r=0;r!=2147483647&&l<=x;l=r+1) { r=x/(x/l); ans-=(r-l+1)*getmu(x/l); } return amu[x]=ans; } int main() { init(); int T; cin>>T; int x; for(int i=1;i<=T;i++) { scanf("%d",&x); printf("%lld %d\n",getphi(x),getmu(x)); } return 0; }