首页 > 代码库 > 一类积性函数的前缀和---刷题记录
一类积性函数的前缀和---刷题记录
题目来源于糖教主浅谈一类积性函数的前缀和...
51Nod 1244 莫比乌斯函数之和
考虑$\mu(x)$的性质：$[n==1]=\sum _{d\mid n} \mu(d)$
可以用上面哪个公式来推导：
$f(n)=\sum _{i=1}^{n}$
$1=\sum _{i=1}^{n} [i==1]$
$=\sum _{i=1}^{n} \sum _{d\mid i} \mu (d)$
$=\sum _{\frac{i}{d}=1}^{n} \sum _{d=1}^{\frac{n}{\frac{i}{d}}} \mu (d)$
$=\sum _{i=1}^{n}\sum _{d=1}^{\frac{n}{i}} \mu(d)$
$=\sum _{i=1}^{n}f(\frac{n}{i})$
$f(n)=1-\sum _{i=2}^{n} f(\frac{n}{i})$
然后，我们预处理出前$\sqrt{n}$个的$f(x)$，然后对于大于$\sqrt{n}$的数的答案，分块递归计算...
复杂度的证明请见糖教主的文章...
代码：
#include<algorithm>#include<iostream>#include<cstring>#include<cstdio>#include<map>//by NeighThornusing namespace std;const int maxn=5000000+5;int cnt,mu[maxn],pri[maxn],vis[maxn];long long n,m,f[maxn];map<long long,long long> mp;inline void prework(void){ mu[1]=1; for(int i=2;i<=5000000;i++){ if(!vis[i]) vis[i]=1,pri[++cnt]=i,mu[i]=-1; for(int j=1;j<=cnt&&1LL*i*pri[j]<=5000000;j++){ vis[i*pri[j]]=1; if(i%pri[j]==0){ mu[i*pri[j]]=0; break; } mu[i*pri[j]]=-mu[i]; } } for(int i=1;i<=5000000;i++) f[i]=f[i-1]+mu[i];}inline long long calc(long long x){ if(x<=5000000) return f[x]; if(mp.find(x)!=mp.end()) return mp[x]; long long ans=1; for(long long i=2,r;i<=x;i=r+1){ r=x/(x/i); ans-=calc(x/i)*(r-i+1); } return mp[x]=ans;}signed main(void){ prework();scanf("%lld%lld",&n,&m); printf("%lld\n",calc(m)-calc(n-1)); return 0;}
51Nod 1239 欧拉函数之和
和上面的题目差不多...
这次利用的是$\phi(x)$的这个性质：$\sum _{d\mid n} \phi(d)=n$
$\phi(n)=n-\sum _{d\mid n d<n}\phi(d)$
$f(n)=\sum _{i=1}^{n} (i-\sum _{d\mid i d<i} \phi(d))$
$=\frac{n(n+1)}{2}-\sum _{i=2}^{n} \sum _{d\mid i d<i} \phi(d)$
$=\frac{n(n+1)}{2}-\sum _{i=2}^{n}\sum _{d=1}^{\frac{n}{i}} \phi(d)$
$=\frac{n(n+1)}{2}-\sum _{i=2}^{n} f(\frac{n}{i})$
代码：
#include<algorithm>#include<iostream>#include<cstring>#include<cstdio>#include<map>//by NeighThornusing namespace std;const int maxn=5000000+5,mod=1e9+7;int cnt,f[maxn],pri[maxn],phi[maxn],vis[maxn];long long n;map<long long,int> mp;inline int mul(long long x,long long y){ int res=0;x%=mod; while(y){ if(y&1) res=(res+x)%mod; x=(x+x)%mod,y>>=1; } return res;}inline int power(int x,int y){ int res=1; while(y){ if(y&1) res=1LL*res*x%mod; x=1LL*x*x%mod,y>>=1; } return res;}inline void prework(void){ phi[1]=1; for(int i=2;i<=5000000;i++){ if(!vis[i]) pri[++cnt]=i,vis[i]=1,phi[i]=i-1; for(int j=1;j<=cnt&&1LL*i*pri[j]<=5000000;j++){ vis[i*pri[j]]=1; if(i%pri[j]==0){ phi[i*pri[j]]=phi[i]*pri[j]; break; } phi[i*pri[j]]=phi[i]*(pri[j]-1); } } for(int i=1;i<=5000000;i++) f[i]=(f[i-1]+phi[i])%mod; }inline int calc(long long n){ if(n<=5000000) return f[n]; if(mp.find(n)!=mp.end()) return mp[n]; int ans=mul(mul(n,n+1),power(2,mod-2)); for(long long i=2,r;i<=n;i=r+1){ r=n/(n/i); ans=(ans-1LL*calc(n/i)*((r-i+1)%mod)%mod+mod)%mod; } return mp[n]=ans;}signed main(void){ prework();scanf("%lld",&n); printf("%lld\n",calc(n)); return 0;}
一类积性函数的前缀和---刷题记录