由简单版中，我们已经推出了
\[\sum_{d=1}^n\mu^2(d)d^{k+1}\sum_{t=1}^{\lfloor {\frac{n}{d}} \rfloor}\mu(t)t^k\sum_{i=1}^{\lfloor {\frac{n}{dt}} \rfloor}\sum_{j=1}^{\lfloor {\frac{n}{dt}} \rfloor}(i+j)^k \]我们设\(T=td\),则
设\(S(x)=\sum_{i=1}^x\sum_{j=1}^x(i+j)^k\)
$\sum_{d=1}^n \mu ^2 (d)d\mu (T/d)\sum_{T=1}^n T^k S(n/T)$
点击查看代码
#include <bits/stdc++.h>
#define speed() ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define ll int
#define ull unsigned long long
#define lid (rt<<1)
#define rid (rt<<1|1)
// #define endl '\n'
//#define int long long
#define pb push_back
// #pragma comment(linker, “/STACK:512000000,512000000”)
using namespace std;
const int N = 1e7+5;
int f[N*2],mu[N*2],F[N*2],pr[N*2],tot,p[N*2],s[N*2];
bool is[N*2];
int n,k;
ll qpow(ll a,ll b)
{
ll ans=1;
while(b)
{
if(b&1)ans=ans*a;
b>>=1;
a=a*a;
}
return ans;
}
void getMu()
{
f[1]=1;mu[1]=1;p[1]=1;
for(int i=2;i<=n*2;i++)
{
if(!is[i])
{
pr[++tot]=i;p[i]=qpow(i,k);
mu[i]=-1;f[i]=i-1;
}
for(int j=1;j<=tot&&i*pr[j]<=2*n;j++)
{
p[i*pr[j]]=p[i]*p[pr[j]];
is[i*pr[j]]=1;
if(i%pr[j]==0)
{
int q=i/pr[j];
if(q%pr[j])f[i*pr[j]]=-pr[j]*f[q];
break;
}
mu[i*pr[j]]=-mu[i];
f[i*pr[j]]=f[i]*(pr[j]-1);
}
}
for(int i=2;i<=2*n;i++)f[i]=f[i-1]+p[i]*f[i],p[i]+=p[i-1];
for(int i=2;i<=2*n;i++)p[i]+=p[i-1];
}
ll calc(ll n)
{
return p[n<<1]-p[n]*2;
}
int main()
{
speed();
// freopen("in.in","r",stdin);
// freopen("out.out","w",stdout);
int T;
cin>>T>>n>>k;
getMu();
while(T--)
{
ll tn;
cin>>tn;
int l=1,r,ans=0;
while(l<=tn)
{
r=tn/(tn/l);
ans+=(f[r]-f[l-1])*calc(tn/l);
l=r+1;
}
// cout<<ans<<endl;
cout<<(ans+(1ll<<32))%(1ll<<32)<<endl;
}
return 0;
}