[hdu6833] a very easy math problem

The question ：

Given a positive integer $T,k,x$, Next $T$ Group example , Each set of examples gives a positive integer $n$, For each $n$, Ask for
$$\sum _{a_1=1}^n\sum _{a_2=1}^n\dots \sum _{a_x=1}^n(\prod _{j=1}^x{a}_j^k)f(gcd(a_1,a_2,\dots ,a_x))gcd(a_1,a_2,\dots ,a_x)$$
among $f(x)$ Is defined as , When $x$ When there is a square factor ,$f(x)=0$, otherwise $f(x)=1$.
$(1\le T\le 10^4,1\le k,x\le 10^9,1\le n\le 2\times 10^5)$

deduction ：

Routine proposal $gcd$, become
$$\sum _{g=1}^n\sum _{a_1=1}^n\sum _{a_2=1}^n\dots \sum _{a_x=1}^n(\prod _{j=1}^x{a}_j^k)f(g)g[g=gcd(a_1,a_2,\dots ,a_x)]$$
Then adjust the formula. ,
$$\sum _{g=1}^{n}g[gNosavestayflatFangbecauseSon]\sum _{a_1=1}^n\sum _{a_2=1}^n\dots \sum _{a_x=1}^n(\prod _{j=1}^x{a}_j^k)[g=gcd(a_1,a_2,\dots ,a_x)]$$
We make $f(g)$,
$$f(g)=\sum _{a_1=1}^n\sum _{a_2=1}^n\dots \sum _{a_x=1}^n(\prod _{j=1}^x{a}_j^k)[g=gcd(a_1,a_2,\dots ,a_x)]$$
then $F(g)={\sum }_{g|d}f(d)$,
$$\begin{gathered} F(g)=\sum _{g|d}f(d)=\sum _{a_1=1}^n\sum _{a_2=1}^n\dots \sum _{a_x=1}^n(\prod _{j=1}^x{a}_j^k)[g|gcd(a_1,a_2,\dots ,a_x)] \\ =\sum _{g|a_1}\sum _{g|a_2}\dots \sum _{g|a_x}(\prod _{j=1}^x{a}_j^k) \\ =\sum _{a_1=1}^{\lfloor \frac{n}{g}\rfloor }\sum _{a_2=1}^{\lfloor \frac{n}{g}\rfloor }\dots \sum _{a_x=1}^{\lfloor \frac{n}{g}\rfloor }(\prod _{j=1}^x{a}_j^k{g}^k) \\ =\sum _{a_1=1}^{\lfloor \frac{n}{g}\rfloor }{a}_1^k{g}^k\sum _{a_2=1}^{\lfloor \frac{n}{g}\rfloor }{a}_2^k{g}^k\dots \sum _{a_x=1}^{\lfloor \frac{n}{g}\rfloor }{a}_x^k{g}^k \\ =g^{xk}(\sum _{a=1}^{\lfloor \frac{n}{g}\rfloor }{a}^k{)}^x \end{gathered}$$
hold $F(g)$ After simplification , It's a little bit easier , Keep it for standby .

Then inversion is carried out against the original formula subset ,
$$\begin{gathered} \sum _{g=1}^{n}g[gnoYesflatFangbecauseSon]f(g)=\sum _{g=1}^n[gnoYesflatFangbecauseSon]\sum _{g|d}\mu (\frac{d}{g})F(d) \\ =\sum _{g=1}^{n}g[gnoYesflatFangbecauseSon]\sum _{g|d}\mu (\frac{d}{g})d^{xk}(\sum _{a=1}^{\lfloor \frac{n}{d}\rfloor }{a}^k{)}^x \end{gathered}$$
It is now ready for preprocessing $({\sum }_{a=1}^{\lfloor \frac{n}{d}\rfloor }{a}^k{)}^x$ then $o(nlogn)$ Did , But it's not complicated enough , We consider number theory blocking .

We use some functions to replace some things in it , Make it look more elegant .

We use it $is(t)$ Express $t$ Is there a square factor , Sometimes for $0$, Otherwise $1$.

Reuse $A(t)=({\sum }_{a=1}^t{a}^k{)}^x$

The original form becomes ,
$$\sum _{g=1}^{n}is(g)g\sum _{g|d}\mu (\frac{d}{g})d^{xk}A(\lfloor \frac{n}{d}\rfloor )$$
The current formula still can't be divided into numbers . Be careful , We are now enumerating $g$, Reuse $d$ enumeration $g$ Multiple . We convert it into enumeration $d$, Enumerate again $d$ Factor of $g$ In the form of , It becomes ,
$$\sum _{d=1}^n{d}^{xk}A(\lfloor \frac{n}{d}\rfloor )\sum _{g|d}\mu (\frac{d}{g})is(g)g$$
Then make $B(d)=d^{xk}{\sum }_{g|d}\mu (\frac{d}{g})is(g)g$, It can be $o(nlogn)$ Pretreated , The formula finally becomes ,
$$\sum _{d=1}^{n}A(\lfloor \frac{n}{d}\rfloor )B(d)$$
ah ！ Isn't this some obvious number theory block .
So we just need to preprocess out $B(d)$ And $SB(d)$, Then preprocess out $A(d)$, Then the number theory is divided into blocks .
The code constant is huge .

Code ：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1000000007;
const ll MAXN=400005;

ll fpow(ll a,ll n)
{
    
    ll sum=1,base=a%mod;
    while(n!=0)
    {
    
        if(n%2)sum=sum*base%mod;
        base=base*base%mod;
        n/=2;
    }
    return sum;
}
ll inv(ll a)
{
    
    return fpow(a,mod-2);
}

ll prime[MAXN+10],notPrime[MAXN+10],mu[MAXN+10],tot;
void initMu(ll n)
{
    
    notPrime[1]=mu[1]=1;
    for(ll i=2;i<=n;i++)
    {
    
        if(!notPrime[i])prime[tot++]=i,mu[i]=-1;
        for(ll j=0;j<tot&&i*prime[j]<=n;j++)
        {
    
            notPrime[i*prime[j]]=1;
            if(i%prime[j])mu[i*prime[j]]=-mu[i];
            else {
    mu[i*prime[j]]=0;break;}
        }
    }
}
ll T,k,x,n;

ll A[400005];
ll is[400005];
ll B[400005];
ll SB[400005];
int main()
{
    
    scanf("%lld%lld%lld",&T,&k,&x);
    initMu(200000);
    for(ll i=2;i*i<=200000;i++)
    {
    
        for(ll j=1;i*i*j<=200000;j++)is[i*i*j]=1;
    }
    for(ll g=1;g<=200000;g++)
    {
    
        for(ll d=g;d<=200000;d+=g)
        {
    
            B[d]=(B[d]+g*mu[d/g]*(1-is[g])%mod)%mod;
        }
    }
    for(ll d=1;d<=200000;d++)B[d]=B[d]*fpow(d,x*k)%mod;
    for(ll d=1;d<=200000;d++)SB[d]=(SB[d-1]+B[d])%mod;
    for(ll d=1;d<=200000;d++)
    {
    
        A[d]=(A[d-1]+fpow(d,k))%mod;
    }
    for(ll d=1;d<=200000;d++)A[d]=fpow(A[d],x);
    while(T--)
    {
    
        scanf("%lld",&n);
        ll ans=0;
        for(ll l=1,r;l<=n;l=r+1)
        {
    
            if(n/l)r=n/(n/l);
            else r=n;
            r=min(r,n);
            ans=(ans+A[n/l]*(SB[r]-SB[l-1])%mod)%mod;
        }
        ans=ans%mod;
        printf("%lld\n",(ans%mod+mod)%mod);
    }
    return 0;
}