首页 > 代码库 > Bzoj3944 Sum
Bzoj3944 Sum
Submit: 3673 Solved: 994
Description
Input
Output
Sample Input
1
2
8
13
30
2333
Sample Output
2 0
22 -2
58 -3
278 -3
1655470 2
HINT
Source
数学问题 dirichlet卷积 莫比乌斯反演
目标函数： $ F(n)=\sum_{i=1}^{n} f(i) $
前缀和函数：$ G(n)=\sum_{i=1}^{n} g(i) $
卷积函数：$g(x)=f(i)*1=\sum_{i|x} f(i)$
用这些就可以搞事情了：
$ G(n)= \sum_{i=1}^{n} g(i)$
$=\sum_{i=1}^{n} \sum_{j|i} f(j) $
$=\sum_{j=1}^{n} \sum_{i=1}^{\lfloor \frac{n}{j} \rfloor} f(i) $
$=\sum_{j=1}^{n} F(\lfloor \frac{n}{j} \rfloor)$
我们要求的是$F(n)$，也就是$F(\lfloor \frac{n}{1} \rfloor)$
把原式移项得到$ F(n)=G(n)-\sum_{j=2}^{n} F(\lfloor \frac{n}{j} \rfloor) $
后面那些F可以分块递归算出。
求 $ \mu $ 的时候，那个卷积卷出来是e（第一项为1，后面为0），即$ G(n)=1 $
求 $ \varphi $的时候，那个卷积卷出来是id（第i项为i），即$G(n)=n*(n+1)/2$
预处理前500w项$ \varphi $ 和 $ \mu $ 的前缀和作为递归边界，就可以愉快地递归计算了。
若$G(n)$可以在$O(1)$时间内算出，则$F(n)$可以在$O(n^{\frac{3}{4}})$的时间内算出
如果预处理前$O(n^{\frac{2}{3}})$的部分，则$F(n)$可以在$O(n^{\frac{2}{3}})$的时间内算出
↑后面那一串F，分块计算的复杂度是 $ O(\sqrt{\frac{n}{k}}) $，递归下去用主定理之类的分析一波即可得出总复杂度（口胡，其实并没有尝试过）
1 #include<iostream> 2 #include<algorithm> 3 #include<cstring> 4 #include<cstdio> 5 #include<cmath> 6 #include<map> 7 #define LL long long 8 using namespace std; 9 const int mxn=5000010;10 LL read(){11 LL x=0,f=1;char ch=getchar();12 while(ch<‘0‘ || ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();}13 while(ch>=‘0‘ && ch<=‘9‘){x=x*10-‘0‘+ch;ch=getchar();}14 return x*f;15 }16 int pri[mxn],cnt=0;17 LL phi[mxn],mu[mxn];18 void init(){19 mu[1]=1;phi[1]=1;20 for(int i=2;i<mxn;i++){21 if(!phi[i]){22 pri[++cnt]=i; phi[i]=i-1; mu[i]=-1;23 }24 for(int j=1;j<=cnt && (LL)pri[j]*i<mxn;j++){25 int tmp=pri[j]*i;26 if(i%pri[j]==0){27 mu[tmp]=0; phi[tmp]=phi[i]*pri[j]; break;28 }29 mu[tmp]=-mu[i];30 phi[tmp]=phi[i]*(pri[j]-1);31 }32 }33 for(int i=2;i<mxn;i++){34 phi[i]+=phi[i-1];35 mu[i]+=mu[i-1];36 }37 return;38 }39 int n;40 map<int,LL>mp,mump;41 LL calc_phi(LL x){42 if(x<mxn)return phi[x];43 if(mp.count(x))return mp[x];44 LL res=(LL)x*(x+1)>>1;45 for(LL i=2,pos;i<=x;i=pos+1){46 LL y=x/i;47 pos=x/y;48 res-=(pos-i+1)*calc_phi(y);49 }50 mp[x]=res;51 return res;52 }53 LL calc_mu(LL x){54 if(x<mxn)return mu[x];55 if(mump.count(x))return mump[x];56 LL res=1;57 for(LL i=2,pos;i<=x;i=pos+1){58 LL y=x/i;59 pos=x/y;60 res-=(pos-i+1)*calc_mu(y);61 }62 mump[x]=res;63 return res;64 }65 int main(){66 int i,j;67 init();68 int T=read();69 while(T--){70 n=read();71 LL ans1=calc_phi(n);72 LL ans2=calc_mu(n);73 printf("%lld %lld\n",ans1,ans2);74 }75 return 0;76 }
Submit: 3673 Solved: 994
[Submit][Status][Discuss]
Description
Input
Output
Sample Input
1
2
8
13
30
2333
Sample Output
2 0
22 -2
58 -3
278 -3
1655470 2
HINT
Source
Bzoj3944 Sum