【题目链接】
https://www.51nod.com/onlineJudge/questionCode.html#!problemId=1239
【题目大意】
计算欧拉函数的前缀和
【题解】
我们知道积性函数∑(phi(d))=n(d|n)
所以∑∑(miu(d))=n*(n+1)/2(d|i){i=1}^{n}
因此我们得到F(n)=n*(n+1)/2-∑F(n/d){d=2}^{n}
同时用hash记忆化phi函数的前缀和
【代码】
#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long LL;
const int mod=1333331,inv2=500000004;
const LL MOD=1e9+7;
LL a,b,miu[5000010],phi[5000010];
int p[500010],cnt=0,i,tot;
bool v[5000010];
struct HASHMAP{
int h[mod+10],cnt,nxt[100010];
LL st[100010],S[100010];
void push(LL k,LL v){
int key=k%mod;
for(int i=h[key];i;i=nxt[i]){
if(S[i]==k)return;
}++cnt;nxt[cnt]=h[key];h[key]=cnt;
S[cnt]=k;st[cnt]=v;
}
LL ask(LL k){
int key=k%mod;
for(int i=h[key];i;i=nxt[i]){
if(S[i]==k)return st[i];
}return -1;
}
}H;
void Get_Prime(){
for(miu[1]=phi[1]=1,i=2;i<=5000000;i++){
if(!v[i])p[tot++]=i,miu[i]=-1,phi[i]=i-1;
for(int j=0;i*p[j]<=5000000&&j<tot;j++){
v[i*p[j]]=1;
if(i%p[j]){
miu[i*p[j]]=-miu[i];
phi[i*p[j]]=phi[i]*(p[j]-1);
}else{
miu[i*p[j]]=0;
phi[i*p[j]]=phi[i]*p[j];
break;
}
}
}for(int i=2;i<=5000000;++i)phi[i]=(phi[i-1]+phi[i])%MOD;
}
LL phi_sum(LL n){
if(n<=5000000)return phi[n];
LL tmp=H.ask(n),la,A=0;
if(tmp!=-1)return tmp;
for(LL i=2;i<=n;i=la+1){
LL now=n/i; la=n/now;
(A+=(la-i+1)%MOD*phi_sum(n/i)%MOD)%=MOD;
}A=((n%MOD)*(n%MOD+1)%MOD*inv2%MOD-A+MOD)%MOD;
H.push(n,A);return A;
}
int main(){
scanf("%lld",&a);
Get_Prime();
printf("%lld\n",phi_sum(a));
return 0;
}