Description
很久很久以前，有一只神犇叫yzy;
很久很久之后，有一只蒟蒻叫lty;
Input
请你读入一个整数N;1<=N<=1E9,A、B模1E9+7;
Output
请你输出一个整数(A=sum_{i=1}^N{mu (i^2)})
请你输出一个整数(B=sum_{i=1}^N{varphi (i^2)})
Sample Input
1
Sample Output
1
1
solution
杜教筛基础题．
对于第一问，由于当(igeqslant 2)的时候(mu(i^2)=0)，所以直接puts("1")就好了．
令
[f(n)=varphi(n^2)=varphi(n)*n\
S(n)=sum_{i=1}^{n}f(i)
]
然后把杜教筛的套路式子搬出来：
[S(n)=sum_{i=1}^{n}(f*g)(i)-sum_{i=2}^{n}g(i)S(lfloorfrac{n}{i}
floor)
]
然后考虑凑出这个(g)．
[(f*g)(n)=sum_{i|n}i*varphi(i)*g(frac{n}{i})
]
看到这个系数(i)很不爽，考虑把他消掉，令(g(n)=n)，得：
[(f*g)(n)=sum_{i|n}i*varphi(i)*frac{n}{i}=n*sum_{i|n}varphi(i)=n^2
]
然后发现这个东西的前缀和很好求，就直接带到套路式里得：
[S(n)=frac{n(n+1)(2n+1)}{6}-sum_{i=2}^niS(lfloorfrac{n}{i}
floor)
]
然后记忆化一下，递归求这个，线筛出前(1e7)就做完了．
#include<bits/stdc++.h>
using namespace std;
#define int long long
void read(int &x) {
x=0;int f=1;char ch=getchar();
for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-f;
for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0';x*=f;
}
void print(int x) {
if(x<0) x=-x,putchar('-');
if(!x) return ;print(x/10),putchar(x%10+48);
}
void write(int x) {if(!x) putchar('0');else print(x);putchar('
');}
const int maxn = 1e7+1;
const int mod = 1e9+7;
int phi[maxn],pri[maxn],vis[maxn],n,tot,inv2,inv6;
void sieve() {
phi[1]=1;
for(int i=2;i<maxn;i++) {
if(!vis[i]) pri[++tot]=i,phi[i]=i-1;
for(int t,j=1;j<=tot&&i*pri[j]<maxn;j++) {
vis[t=i*pri[j]]=1;
if(!(i%pri[j])) {phi[t]=phi[i]*pri[j];break;}
phi[t]=phi[i]*phi[pri[j]];
}
}
for(int i=1;i<maxn;i++) phi[i]=(phi[i-1]+phi[i]*i)%mod;
}
map<int,int > Phi;
int qpow(int a,int x) {
int res=1;
for(;x;x>>=1,a=a*a%mod) if(x&1) res=res*a%mod;
return res;
}
int calc(int n) {return n%mod*(n%mod+1)%mod*inv2%mod;}
int sum(int n) {
if(n<maxn) return phi[n];
if(Phi[n]) return Phi[n];
int res=n*(n+1)%mod*(n+n+1)%mod*inv6%mod;
int T=2;//printf("%lld
",Phi[n]);
while(T<=n) {
int pre=T;T=n/(n/T);
res=(res-sum(n/T)*(calc(T)-calc(pre-1))%mod)%mod;T++;
}
return Phi[n]=(res%mod+mod)%mod;
}
signed main() {
sieve();inv2=qpow(2,mod-2);inv6=qpow(6,mod-2);
int n;read(n);write(1ll),write(sum(n));
return 0;
}