学到了好多东西啊这题。。。
https://blog.csdn.net/sdfzyhx/article/details/72968468
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+,mod=1e9+;
typedef long long ll;
ll miu[N],v[N],p[N],cnt,sum1[N],sum2[N],mi1[N],mi2[N],h[N],g[N],f[N],T,n;
ll inc(ll a,ll b)
{
a=a+b;
if(a>mod)a%=mod;
return a;
}
ll dec(ll a,ll b)
{
a=a-b;
if(a<)a+=mod;
return a%mod;
}
ll qmod(ll x,ll y)
{
int ans=;
while(y)
{
if(y&)ans=1ll*ans*x%mod;
x=1ll*x*x%mod;y>>=;
}
return ans;
}
void init()
{
miu[]=sum1[]=sum2[]=mi1[]=mi2[]=;
for(int i=;i<=1e6;++i)
{
if(!v[i])
{
p[++cnt]=i;
miu[i]=-;
sum1[i]=i+;
sum2[i]=inc(1ll*i*i%mod+i,);
mi1[i]=mi2[i]=i;
}
for(int j=;j<=cnt&&i*p[j]<=1e6;++j)
{
int x=i*p[j];v[x]=;
if(i%p[j])
{
mi1[x]=mi2[x]=p[j];
miu[x]=-miu[i];
sum1[x]=1ll*sum1[i]*sum1[p[j]]%mod;
sum2[x]=1ll*sum2[i]*sum2[p[j]]%mod;
}
else
{
mi1[x]=p[j];
mi2[x]=1ll*mi2[i]*p[j]%mod;
sum1[x]=inc(sum1[i],1ll*p[j]*mi2[i]%mod*sum1[i/mi2[i]]%mod);//求约数和
sum2[x]=inc(sum2[i],1ll*inc(1ll*mi2[i]*mi2[i]%mod*mi1[i]%mod,1ll*mi2[i]*mi2[i]%mod*mi1[i]%mod*mi1[i]%mod)*sum2[i/mi2[i]]%mod);//求平方约数和
break;
}
}
}
for(int i=;i<=1e6;++i)
{
h[i]=inc(h[i-],sum1[i]);
g[i]=1ll*i*sum1[i]%mod*h[i]%mod;
sum2[i]=1ll*sum2[i]*i%mod;
sum2[i]=inc(sum2[i],sum2[i-]);
}
for(int i=;i<=1e6;++i)
{ for(int j=i,k=;j<=1e6;j+=i,k++)
f[j]=inc(f[j],1ll*miu[i]%mod*i%mod*i%mod*g[k]%mod);
f[i]=inc(f[i],f[i-]);
}
return;
}
int main()
{
init();scanf("%d",&T);
for(int i=;i<=T;++i)
{
scanf("%d",&n);
printf("Case #%d: %lld\n",i,(dec(2ll*f[n]%mod,sum2[n])+mod)%mod);
}
return ;
}