Description
求(sum_{i=1}^nvarphi(i),sum_{i=1}^nmu(i),nleqslant 2 imes 10^9)
Solution
杜教筛...
总之杜教筛就是通过这样一个式子来求积性函数前缀和(S(n))
因为(sum_{i=1}^nsum_{dmid i}g(d)f(frac{i}{d})=sum_{i=1}^ng(i)S(lfloorfrac{n}{i} floor))
同时将等式右边(g(1)S(n))提出来就可以得到(g(1)S(n)=sum_{i=1}^nsum_{dmid i}g(d)f(frac{i}{d})-sum_{i=2}^ng(i)S(lfloorfrac{n}{i} floor))
如果能够直接算出来前面的式子,后面的式子可以分块...加上记忆化...可以做到(O(n^{frac{2}{3}}))的复杂度...不太会证明...
对于(varphi(n)),有一个式子...(sum_{dmid n}varphi(d)=n)...那么令(g(n)=1)即可...
(sum_{i=1}^nsum_{dmid i}varphi(d)=sum_{i=1}^n i=frac{n(n+1)}{2})
对于(mu(n)),有一个式子...(sum_{dmid n}mu(d)=[n=1])...所以依然令(g(n)=1)...
那么(sum_{i=1}^nsum_{dmid i}mu(d)=1)...
没了...
Code
/************************************************************** Problem: 3944 User: BeiYu Language: C++ Result: Accepted Time:7680 ms Memory:56128 kb ****************************************************************/ #include <bits/stdc++.h> using namespace std; #define mpr make_pair typedef long long ll; typedef pair<ll,ll> pr; const int N = 2000500; int b[N],pm[N],cp; int mu[N],phi[N],sm[N]; ll sp[N]; void pre(int n) { for(int i=2;i<=n;i++) { if(!b[i]) pm[++cp]=i,mu[i]=-1,phi[i]=i-1; for(int j=1;j<=cp && i*pm[j]<=n;j++) { b[i*pm[j]]=1; if(i%pm[j]) mu[i*pm[j]]=-mu[i],phi[i*pm[j]]=phi[i]*(pm[j]-1); else { phi[i*pm[j]]=phi[i]*pm[j];break; } } } mu[1]=phi[1]=1; for(int i=1;i<=n;i++) sm[i]=sm[i-1]+mu[i],sp[i]=sp[i-1]+phi[i];; } map<ll,pr> mp; pr operator - (const pr &a,const pr &b) { return mpr(a.first-b.first,a.second-b.second); } pr operator * (const pr &a,const ll b) { return mpr(a.first*b,a.second*b); } pr S(ll n) { if(n<=2000000) return mpr(sm[n],sp[n]); if(mp.count(n)) return mp[n]; ll f1=1,f2; if(n&1) f2=n*((n+1)>>1);else f2=(n>>1)*(n+1); pr fn=mpr(f1,f2); for(ll i=2,j;i<=n;i=j+1) { j=n/(n/i); fn=fn-S(n/i)*(j-i+1); }return mp[n]=fn; } int main() { int T;ll n; for(pre(2000000),scanf("%d",&T);T--;) { scanf("%lld",&n); pr ans=S(n); printf("%lld %lld ",ans.second,ans.first); }return 0; }