A Very Easy Math Problem
题意:
给定 n , x , k n,x,k n,x,k,求解:
∑ a 1 = 1 n ∑ a 2 = 1 n . . . ∑ a x = 1 n ( ∏ j = 1 x a j k ) f ( g c d ( a 1 , a 2 , . . . , a x ) ) ∗ g c d ( a 1 , a 2 , . . . , a x ) \sum_{a_1=1}^{n}\sum_{a_2=1}^{n}...\sum_{a_x=1}^{n}(\prod_{j=1}^{x}a_{j}^{k})f(gcd(a_1,a_2,...,a_x))*gcd(a_1,a_2,...,a_x) a1=1∑na2=1∑n...ax=1∑n(j=1∏xajk)f(gcd(a1,a2,...,ax))∗gcd(a1,a2,...,ax)
其中
f ( x ) = { 0 , ( k 2 ∣ x ) a n d ( k ! = 1 ) 1 , e l s e f(x)=\begin{cases}0,(k^2|x)\ and \ (k!=1) \\1,else \end{cases} f(x)={ 0,(k2∣x) and (k!=1)1,else
Solution:
∑ a 1 = 1 n ∑ a 2 = 1 n . . . ∑ a x = 1 n ( ∏ j = 1 x a j k ) f ( g c d ( a 1 , a 2 , . . . , a x ) ) ∗ g c d ( a 1 , a 2 , . . . , a x ) = ∑ g = 1 n ∑ a 1 = 1 n ∑ a 2 = 1 n . . . ∑ a x = 1 n ( ∏ j = 1 x a j k ) f ( g ) ∗ g ∗ [ g c d ( a 1 , a 2 , . . . , a x ) = g ] = ∑ g = 1 n f ( g ) ∗ g ∑ a 1 = 1 n ∑ a 2 = 1 n . . . ∑ a x = 1 n ( ∏ j = 1 x a j k ) [ g c d ( a 1 g , a 2 g , . . . , a x g ) = 1 ] = ∑ g = 1 n f ( g ) ∗ g ∑ a 1 = 1 ⌊ n g ⌋ ∑ a 2 = 1 ⌊ n g ⌋ . . . ∑ a x = 1 ⌊ n g ⌋ ( ∏ j = 1 x a j k g k ) ∑ d ∣ g c d ( a 1 , a 2 , . . . a x ) μ ( d ) = ∑ g = 1 n f ( g ) ∗ g ∗ g x k ∑ a 1 = 1 ⌊ n g ⌋ a 1 k ∑ a 2 = 1 ⌊ n g ⌋ a 2 k . . . ∑ a x = 1 ⌊ n g ⌋ a x k ∑ d ∣ g c d ( a 1 , a 2 , . . . a x ) μ ( d ) = ∑ g = 1 n f ( g ) ∗ g ∗ g x k ∑ d = 1 ⌊ n d ⌋ μ ( d ) ( ∑ a = 1 ⌊ n g d ⌋ a k d k ) x \sum_{a_1=1}^{n}\sum_{a_2=1}^{n}...\sum_{a_x=1}^{n}(\prod_{j=1}^{x}a_{j}^{k})f(gcd(a_1,a_2,...,a_x))*gcd(a_1,a_2,...,a_x) \\ =\sum_{g=1}^n\sum_{a_1=1}^{n}\sum_{a_2=1}^{n}...\sum_{a_x=1}^{n}(\prod_{j=1}^{x}a_{j}^{k})f(g)*g*[gcd(a_1,a_2,...,a_x)=g] \\ =\sum_{g=1}^nf(g)*g\sum_{a_1=1}^{n}\sum_{a_2=1}^{n}...\sum_{a_x=1}^{n}(\prod_{j=1}^{x}a_{j}^{k})[gcd(\frac{a_1}{g},\frac{a_2}{g},...,\frac{a_x}{g})=1] \\ =\sum_{g=1}^{n}f(g)*g\sum_{a_1=1}^{\lfloor\frac{n}{g}\rfloor}\sum_{a_2=1}^{\lfloor\frac{n}{g}\rfloor}...\sum_{a_x=1}^{\lfloor\frac{n}{g}\rfloor}(\prod_{j=1}^{x}a_{j}^{k}g^k)\sum_{d|gcd(a_1,a_2,...a_x)}\mu(d) \\ =\sum_{g=1}^{n}f(g)*g*g^{xk}\sum_{a_1=1}^{\lfloor\frac{n}{g}\rfloor}a_1^k\sum_{a_2=1}^{\lfloor\frac{n}{g}\rfloor}a_2^k...\sum_{a_x=1}^{\lfloor\frac{n}{g}\rfloor}a_x^k\sum_{d|gcd(a_1,a_2,...a_x)}\mu(d) \\ =\sum_{g=1}^nf(g)*g*g^{xk}\sum_{d=1}^{\lfloor\frac{n}{d}\rfloor}\mu(d)(\sum_{a=1}^{\lfloor\frac{n}{gd}\rfloor}a^kd^k)^x a1=1∑na2=1∑n...ax=1∑n(j=1∏xajk)f(gcd(a1,a2,...,ax))∗gcd(a1,a2,...,ax)=g=1∑na1=1∑na2=1∑n...ax=1∑n(j=1∏xajk)f(g)∗g∗[gcd(a1,a2,...,ax)=g]=g=1∑nf(g)∗ga1=1∑na2=1∑n...ax=1∑n(j=1∏xajk)[gcd(ga1,ga2,...,gax)=1]=g=1∑nf(g)∗ga1=1∑⌊gn⌋a2=1∑⌊gn⌋...ax=1∑⌊gn⌋(j=1∏xajkgk)d∣gcd(a1,a2,...ax)∑μ(d)=g=1∑nf(g)∗g∗gxka1=1∑⌊gn⌋a1ka2=1∑⌊gn⌋a2k...ax=1∑⌊gn⌋axkd∣gcd(a1,a2,...ax)∑μ(d)=g=1∑nf(g)∗g∗gxkd=1∑⌊dn⌋μ(d)(a=1∑⌊gdn⌋akdk)x
假设T=gd,那么
∑ g = 1 n f ( g ) ∗ g ∗ g x k ∑ d = 1 ⌊ n d ⌋ μ ( d ) ∗ d x k ( ∑ a = 1 ⌊ n g d ⌋ a k ) x = ∑ g = 1 n f ( g ) ∗ g ∗ g x k ∑ g ∣ T μ ( T g ) ∗ ( T g ) x k ( ∑ a = 1 ⌊ n T ⌋ a k ) x = ∑ T = 1 n T x k ( ∑ g ∣ T f ( g ) ∗ g ∗ μ ( T g ) ) ( ∑ a = 1 ⌊ n T ⌋ a k ) x \sum_{g=1}^nf(g)*g*g^{xk}\sum_{d=1}^{\lfloor\frac{n}{d}\rfloor}\mu(d)*d^{xk}(\sum_{a=1}^{\lfloor\frac{n}{gd}\rfloor}a^k)^x \\ =\sum_{g=1}^{n}f(g)*g*g^{xk}\sum_{g|T}\mu(\frac{T}{g})*(\frac{T}{g})^{xk}(\sum_{a=1}^{\lfloor\frac{n}{T}\rfloor}a^k)^x \\ =\sum_{T=1}^{n}T^{xk}(\sum_{g|T}f(g)*g*\mu(\frac{T}{g}))(\sum_{a=1}^{\lfloor\frac{n}{T}\rfloor}a^k)^x g=1∑nf(g)∗g∗gxkd=1∑⌊dn⌋μ(d)∗dxk(a=1∑⌊gdn⌋ak)x=g=1∑nf(g)∗g∗gxkg∣T∑μ(gT)∗(gT)xk(a=1∑⌊Tn⌋ak)x=T=1∑nTxk(g∣T∑f(g)∗g∗μ(gT))(a=1∑⌊Tn⌋ak)x
之后前缀和+整除分块就可以求解了。
代码
#include<bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
typedef long long ll;
const int mod=1e9+7;
const int N=2e5;
int mu[N+5],prime[N+5],notPrime[N+5],cnt=0,is[N+5];
ll sum[N+5];
ll fpow(ll x,ll power)
{
ll ans=1;
while(power)
{
if(power&1)ans=ans*x%mod;
power>>=1;
x=x*x%mod;
}
return ans;
}
void init()
{
mu[1]=is[1]=1;
for(int i=2;i<=N;i++)
{
if(!notPrime[i])
{
prime[cnt++]=i;
mu[i]=-1;
is[i]=1;
}
for(int j=0;j<cnt&&1ll*i*prime[j]<=N;j++)
{
notPrime[i*prime[j]]=1;
if(i%prime[j]==0)break;
mu[i*prime[j]]=-mu[i];
is[i*prime[j]]=is[i];
}
}
}
int t,k,x;
ll a[200005];
int main()
{
init();
scanf("%d%d%d",&t,&k,&x);
for(int i=1;i<=N;i++)a[i]=(a[i-1]+fpow(i,k))%mod;
for(int i=1;i<=N;i++)a[i]=fpow(a[i],x);
for(int i=1;i<=N;i++)
{
for(int j=1;j<=N/i;j++)
sum[i*j]=(sum[i*j]+1ll*j*is[j]*mu[i]%mod)%mod;
}
for(int i=1;i<=N;i++)sum[i]=(sum[i]*fpow(i,1ll*k*x)%mod+sum[i-1])%mod;
while(t--)
{
int n;scanf("%d",&n);
ll res=0;
for(int l=1,r;l<=n;l=r+1)
{
r=n/(n/l);
res=(res+1ll*(sum[r]-sum[l-1])*a[n/l]%mod)%mod;
}
res=(res+mod)%mod;
printf("%lld\n",res);
}
return 0;
}