题目
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
题解
第一问…恒等于$1$送分qwq
第二问，可以发现$\phi(i^2)=i\phi(i)$
来自$AH$的证明：
证这个就是证若$\gcd(x,y)=1$，则有$\gcd(x^2,y+kx)=1$；若$\gcd(x,y)!=1$，则有$\gcd(x^2,y+kx)!=1$
设$y=ax+b$，其中$\gcd(b,x)=1$，则$\gcd(x^2,y+kx)=\gcd(x^2,(a+k)x+b)$，可以发现$(a+k)x+b$与$x$还是互质的，即与$x^2$互质
不互质同理
因为$n\le 1e9$，所以用杜教筛处理这个式子
设$t(i)=i\phi(i)$，$S(n)=\sum_{i=1}^{n}t(i)$
设个积性函数$f$,则$f(1)S(n)=\sum_{i=1}^{n}(f*t)(i)-\sum_{i=2}^{n}f(i)S(\left\lfloor\frac{n}{i}\right\rfloor)$
其中$(f*t)(i)=\sum_{d\vert i}t(d)f(\frac{i}{d})$
设$f(i)=i$，则$\sum_{d\vert i}t(d)f(\frac{i}{d})=\sum_{d\vert i}\phi(d)d\frac{i}{d}=i\sum_{d\vert i}\phi(d)$，后面部分就是$i$，所以答案就是$i^2$
所以$S(n)=\sum_{i=1}^{n}i^2-\sum_{i=2}^{n}iS(\left\lfloor\frac{n}{i}\right\rfloor)$，这个式子就可以处理了
代码
# include<iostream>
# include<cstring>
# include<cstdio>
# include<algorithm>
# define LL long long
using namespace std;
const int MAX=2e6+1,mod=1e9+7,inv2=5e8+4,inv6=166666668;
int n,tot;
int pm[MAX];
LL phi[MAX],ph[MAX];
bool use[MAX];
LL S(LL x)
{
return x*(x+1)%mod*(x+x+1)%mod*inv6%mod;
}
LL SS(LL x)
{
return x*(x+1)%mod*inv2%mod;
}
LL dfs(LL x)
{
if(x<MAX) return phi[x];
LL tt=n/x;
if(ph[tt]) return ph[tt];
ph[tt]=S(x);
for(int l=2,r;l<=x;l=r+1)
r=x/(x/l),ph[tt]=(ph[tt]-(SS(r)-SS(l-1))*dfs(x/l))%mod;
return (ph[tt]+mod)%mod;
}
int main()
{
scanf("%d",&n),printf("1\n");
phi[1]=1;
for(int i=2;i<MAX;++i)
{
if(!use[i]) pm[++tot]=i,phi[i]=i-1;
for(int j=1;j<=tot&&pm[j]*i<MAX;++j)
{
use[i*pm[j]]=1;
if(i%pm[j]==0)
{
phi[i*pm[j]]=pm[j]*phi[i];
break;
}
phi[i*pm[j]]=phi[i]*phi[pm[j]];
}
}
for(int i=2;i<MAX;++i)
phi[i]=(1ll*i*phi[i]%mod+phi[i-1])%mod;
if(n<MAX) return printf("%lld",phi[n]);
return printf("%lld",dfs(n)),0;
}
