Description
\[ sum_G(n)=\sum_{i=1}^n \mu(i^2)\\sum_F(n)=\sum_{i=1}^n \phi(i^2) \]
Solution
For all cases,\(G(n)=n\)
Because \(G(i^2)=[i==1]\)
\[ \begin{equation} \begin{split} F(n)&=\sum_{i=1}^n \phi(i^2)\\ &=\sum_{i=1}^{n} i\cdot \phi(i)\\ \end{split} \end{equation}\\ \]
\[ \begin{equation} \begin{split} &\sum_{i=1}^n\sum_{d|i}d \cdot \phi(d)\cdot\frac{i}{d}\\=&\sum_{i=1}^ni\cdot \sum_{d|i}d\cdot\phi(d)\\ =&\sum_{i=1}^ni^2 \\=&\frac{n(n+1)(2n+1)}{6} \end{split} \end{equation} \]
\[ \sum_{i=1}^n(Id*F)(i)=\frac{n(n+1)(2n+1)}{6} \]
\[ \begin{equation} \begin{split} Sum_F(n)=&\sum_{i=1}^n(Id*F)(i)-\sum_{i=2}^{n}i\cdot F(\lfloor\frac{n}{i}\rfloor)\\ =&\frac{n(n+1)(2n+1)}{6}-\sum_{i=2}^{n}i\cdot F(\lfloor\frac{n}{i}\rfloor) \end{split} \end{equation} \]
Code
#include#define reg registerusing namespace std;inline int read(){ int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();} return x*f;}const int MN=1e9,MX=1e6+5,M=1e6,mod=1e9+7,inv6=166666668,inv2=500000004;int N,F[MX],phi[MX];int Mul(int x,int y){return 1ll*x*y%mod;}int Add(int x,int y){return (x+y)%mod;}void init(){ static int prime[MX],tot; static bool mark[MX]; reg int i,j; phi[1]=1; for(i=2;i<=M;++i) { if(!mark[i]){prime[++tot]=i;phi[i]=i-1;} for(j=1;j<=tot&&i*prime[j]<=M;++j) { mark[i*prime[j]]=true; if(i%prime[j]==0){phi[i*prime[j]]=Mul(phi[i],prime[j]);break;} else phi[i*prime[j]]=Mul(phi[i],phi[prime[j]]); } } for(i=1;i<=M;++i) phi[i]=Add(Mul(phi[i],i),phi[i-1]);}int S(int x){return Mul(x,Mul(x+1,inv2));}int calc(int n){ if(n<=M) return phi[n]; if(F[N/n]) return F[N/n]; int res=Mul(Mul((n+1),Mul((2*n+1),n)),inv6); for(int l=2,r;l<=n;l=r+1) { r=n/(n/l); res=Add(res,mod-Mul(Add(S(r),mod-S(l-1)),calc(n/l))); } return F[N/n]=res;}int main(){ N=read(); puts("1");init(); printf("%lld\n",calc(N)); return 0;}
Blog来自PaperCloud，未经允许，请勿转载，TKS！