放在这里待办
定义
\[g(n)=2\sum ^n_{i=2}\left \lfloor \frac{n}{i} \right \rfloor^2 \phi(i)+n^2
\]
求 \(g(n)\)
定义
\[f(n)=\frac{g(n)-n^2}{2}
\]
则
\[f(n)=\sum ^n_{i=2}\left \lfloor \frac{n}{i} \right \rfloor^2 \phi(i)
\]
\[f(n-1)=\sum ^{n-1}_{i=2}\left \lfloor \frac{n-1}{i} \right \rfloor^2 \phi(i)
\]
\[f(n)-f(n-1)=\sum ^{}_{i|n}((\frac {n}{i})^2-(\frac {n}{i}-1)^2)\phi(i)
\]
\[=2\sum ^{}_{i|n}\frac {n}{i}\phi(i) - n
\]
定义
\[g(n)=2f(n)+n^2
\]
则
\[sum_g=2sum_f+\frac{n(n+2)(2n+1)}{6}
\]
#include<bits/stdc++.h>//记得开int128
#define int long long
#define ll __int128
using namespace std;
const int N=1e7+5;
int p[N],cnt,phi[N],s[N],low[N],T,sum[N],sums[N];
bool isp[N];
unordered_map<int,int>ans;
void Euler(int n){s[1]=low[1]=phi[1]=isp[1]=sum[1]=1;for(int i=2;i<=n;i++){if(!isp[i])p[++cnt]=i,phi[i]=i-1,s[i]=2*i-1,low[i]=i;sum[i]=sum[i-1]+phi[i],sums[i]=sums[i-1]+2*s[i]-i;for(int j=1;j<=cnt&&i*p[j]<=n;j++){isp[i*p[j]]=1;if(i%p[j]==0){low[i*p[j]]=low[i]*p[j],phi[i*p[j]]=phi[i]*p[j];if(low[i]==i){s[i*p[j]]=s[i]*p[j]+phi[i*p[j]];}else{s[i*p[j]]=s[i/low[i]]*s[low[i]*p[j]];}break;}low[i*p[j]]=p[j],s[i*p[j]]=s[i]*s[p[j]],phi[i*p[j]]=phi[i]*phi[p[j]];}}for (int i=1;i<=10;i++) cout<<s[i]<<" "; cout<<"\n";
}
int djs(int n){if(n<=N-5)return sum[n];if(ans[n])return ans[n];__int128 res=(__int128)n*(n+1)/2;for(int l=2,r;l<=n;l=r+1){r=n/(n/l);res-=(r-l+1)*djs(n/l);}return ans[n]=res;
}
signed main(){freopen("1.in","r",stdin);// freopen("1.out","w",stdout);cin>>T;Euler(N-5);while(T--){int n;cin>>n;if(n<=N-5){cout<<2*s[n]+n*n<<endl;continue;}int res=0;for(int l=1,r;l<=n;l=r+1){r=n/(n/l);res+=(djs(r)-djs(l-1))*(n/l)*(n/l);}cout<<2*res-n*n<<endl;}
}