参考陈牧歌在apio2018的讲课课件
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
typedef long long ll;
ll n;
int pri[4641590], cnt, phi[4641590], msh[1544665][2];
bool isp[4641590];
const int mod=1000000007;
int getHash(ll x){
int p=x%1544657;
while(msh[p][0] && msh[p][0]!=x) p = (p + 1) % 1544657;
return p;
}
int getPhi(ll x){
if(x<=4641581) return phi[x];
int p=getHash(x);
if(msh[p][0]) return msh[p][1];
msh[p][0] = x;
ll lst, re=0;
for(ll i=2; i<=x; i=lst+1){
lst = x / (x / i);
ll tmp=(ll)getPhi(x/i) * (lst-i+1) % mod;
re = (re + tmp) % mod;
}
x %= mod;
re = ((ll)x * (x + 1) % mod * 500000004 % mod - re + mod) % mod;
msh[p][1] = re;
return re;
}
int main(){
memset(isp, true, sizeof(isp));
isp[0] = isp[1] = false;
phi[1] = 1;
for(int i=2; i<=4641581; i++){
if(isp[i]) pri[++cnt] = i, phi[i] = i - 1;
for(int j=1; j<=cnt && i*pri[j]<=4641581; j++){
isp[i*pri[j]] = false;
if(i%pri[j]==0){
phi[i*pri[j]] = phi[i] * pri[j];
break;
}
else phi[i*pri[j]] = phi[i] * (pri[j] - 1);
}
}
for(int i=2; i<=4641581; i++)
phi[i] = (phi[i-1] + phi[i]) % mod;
cin>>n;
cout<<getPhi(n)<<endl;
return 0;
}