思路：杜教筛
提交：(2)次
错因：(varphi(i))的前缀和用(int)存的
题解：
对于一类筛积性函数前缀和的问题，杜教筛可以以低于线性的时间复杂度来解决问题。
先要构造(h=f*g)，并且(h)的前缀和易求，(g)的区间和易求。
具体地：
[sum_{i=1}^{n}h(i)=sum_{i=1}^{n}sum_{d|i}g(d)cdot f(frac{i}{d})$$ $$sum_{i=1}^{n}h(i)=sum_{d=1}^{n}g(d)sum_{i=1}^{lfloorfrac{n}{d}
floor}f({i})
]
设(S(n))表示(sum_{i=1}^{n}f(i))
[sum_{i=1}^{n}h(i)=sum_{d=1}^{n}g(d)cdot S(lfloorfrac{n}{d}
floor)
]
[g(1)cdot S(n)=sum_{i=1}^{n}h(i)-sum_{d=2}^{n}g(d)cdot S(lfloorfrac{n}{d}
floor)
]
当我们对后面的式子进行整除分块时，求(S(n))的复杂度为(O(n^{frac{2}{3}}))
所以主要就是如何构造(h)和(g)
好吧直接说了：
(epsilon=mucdot I)
(id=varphicdot I)
对于(f(n)=varphi(n)cdot n^k=varphi(n^{k+1}))的一类方法：
(id^{k+1}=fcdot id^k)
#include<cstdio>
#include<iostream>
#include<unordered_map>
#include<cmath>
#define ll long long
#define R register int
using namespace std;
namespace Luitaryi {
template<class I> inline I g(I& x) { x=0; register I f=1;
register char ch; while(!isdigit(ch=getchar())) f=ch=='-'?-1:f;
do x=x*10+(ch^48); while(isdigit(ch=getchar())); return x*=f;
} const int N=5000000,Inf=2147483647;
int T,n,cnt,p[N/4],mu[N+10];
ll phi[N+10];
bool v[N+10];
inline void PRE() { phi[1]=mu[1]=1;
for(R i=2;i<=N;++i) {
if(!v[i]) p[++cnt]=i,phi[i]=i-1,mu[i]=-1;
for(R j=1;j<=cnt&&i*p[j]<=N;++j) {
v[i*p[j]]=true;
if(i%p[j]==0) {
mu[i*p[j]]=0;
phi[i*p[j]]=phi[i]*p[j]; break;
} mu[i*p[j]]=-mu[i];
phi[i*p[j]]=phi[i]*(p[j]-1);
}
}
for(R i=1;i<=N;++i) mu[i]+=mu[i-1];
for(R i=1;i<=N;++i) phi[i]+=phi[i-1];
}
unordered_map<int,int> memmu;
unordered_map<int,ll> memphi;
inline ll s_phi(int n) {
if(n<=N) return phi[n];
if(memphi.count(n)) return memphi[n];
register ll ans=0;
for(R l=2,r;r<Inf&&l<=n;l=r+1) {
r=n/(n/l),ans+=(r-l+1)*s_phi(n/l);
} return memphi[n]=1llu*n*(n+1ll)/2ll-ans;
}
inline int s_mu(int n) {
if(n<=N) return mu[n];
if(memmu.count(n)) return memmu[n];
register ll ans=0;
for(R l=2,r;r<Inf&&l<=n;l=r+1) {
r=n/(n/l),ans+=(r-l+1)*s_mu(n/l);
} return memmu[n]=1ll-ans;
}
inline void main() {
PRE(); g(T); while(T--) {
g(n); printf("%lld %d
",s_phi(n),s_mu(n));
}
}
} signed main() {Luitaryi::main(); return 0;}
2019.08.23
77