题意
给你
n
,
m
,
d
,
k
n,m,d,k
n,m,d,k计算下列式子
∑
i
1
=
1
m
∑
i
2
=
1
m
∑
i
3
=
1
m
⋯
∑
i
n
=
1
m
[
g
c
d
(
i
1
,
i
2
,
i
3
,
⋯
,
i
n
)
=
=
d
]
(
i
1
i
2
i
3
⋯
i
n
)
k
\sum_{i_1=1}^m\sum_{i_2=1}^m\sum_{i_3=1}^m\cdots\sum_{i_n=1}^m[gcd(i_1,i_2,i_3,\cdots,i_n)==d](i_1i_2i_3\cdots i_n)^k
i1=1∑mi2=1∑mi3=1∑m⋯in=1∑m[gcd(i1,i2,i3,⋯,in)==d](i1i2i3⋯in)k
其中
1
≤
n
≤
1
0
100000
,
1
≤
m
,
d
≤
100000
,
1
≤
k
≤
1
0
9
1\le n\le 10^{100000},1\le m,d\le100000,1\le k\le10^9
1≤n≤10100000,1≤m,d≤100000,1≤k≤109
思路
先提出一个
d
d
d
∑
i
1
=
1
m
d
∑
i
2
=
1
m
d
∑
i
3
=
1
m
d
⋯
∑
i
n
=
1
m
d
[
g
c
d
(
i
1
,
i
2
,
i
3
,
⋯
,
i
n
)
=
=
1
]
d
k
n
(
i
1
i
2
i
3
⋯
i
n
)
k
\sum_{i_1=1}^{\frac{m}{d}}\sum_{i_2=1}^{\frac{m}{d}}\sum_{i_3=1}^{\frac{m}{d}}\cdots\sum_{i_n=1}^{\frac{m}{d}}[gcd(i_1,i_2,i_3,\cdots,i_n)==1]d^{kn}(i_1i_2i_3\cdots i_n)^k
i1=1∑dmi2=1∑dmi3=1∑dm⋯in=1∑dm[gcd(i1,i2,i3,⋯,in)==1]dkn(i1i2i3⋯in)k
d
k
n
∑
i
1
=
1
m
d
∑
i
2
=
1
m
d
∑
i
3
=
1
m
d
⋯
∑
i
n
=
1
m
d
[
g
c
d
(
i
1
,
i
2
,
i
3
,
⋯
,
i
n
)
=
=
1
]
(
i
1
i
2
i
3
⋯
i
n
)
k
d^{kn}\sum_{i_1=1}^{\frac{m}{d}}\sum_{i_2=1}^{\frac{m}{d}}\sum_{i_3=1}^{\frac{m}{d}}\cdots\sum_{i_n=1}^{\frac{m}{d}}[gcd(i_1,i_2,i_3,\cdots,i_n)==1](i_1i_2i_3\cdots i_n)^k
dkni1=1∑dmi2=1∑dmi3=1∑dm⋯in=1∑dm[gcd(i1,i2,i3,⋯,in)==1](i1i2i3⋯in)k
再将
∑
j
∣
g
c
d
(
i
1
,
i
2
,
i
3
,
⋯
,
i
n
)
μ
(
j
)
=
[
g
c
d
(
i
1
,
i
2
,
i
3
,
⋯
,
i
n
)
=
=
1
]
\sum_{j|gcd(i_1,i_2,i_3,\cdots,i_n)}\mu(j)=[gcd(i_1,i_2,i_3,\cdots,i_n)==1]
∑j∣gcd(i1,i2,i3,⋯,in)μ(j)=[gcd(i1,i2,i3,⋯,in)==1]带入
d
k
n
∑
i
1
=
1
m
d
∑
i
2
=
1
m
d
∑
i
3
=
1
m
d
⋯
∑
i
n
=
1
m
d
∑
j
∣
g
c
d
(
i
1
,
i
2
,
i
3
,
⋯
,
i
n
)
μ
(
j
)
(
i
1
i
2
i
3
⋯
i
n
)
k
d^{kn}\sum_{i_1=1}^{\frac{m}{d}}\sum_{i_2=1}^{\frac{m}{d}}\sum_{i_3=1}^{\frac{m}{d}}\cdots\sum_{i_n=1}^{\frac{m}{d}}\sum_{j|gcd(i_1,i_2,i_3,\cdots,i_n)}\mu(j)(i_1i_2i_3\cdots i_n)^k
dkni1=1∑dmi2=1∑dmi3=1∑dm⋯in=1∑dmj∣gcd(i1,i2,i3,⋯,in)∑μ(j)(i1i2i3⋯in)k
原来是枚举
g
c
d
gcd
gcd的因子我们可以换成枚举他的倍数
d
k
n
∑
j
=
1
m
d
μ
(
j
)
∑
i
1
=
1
m
d
j
∑
i
2
=
1
m
d
j
∑
i
3
=
1
m
d
j
⋯
∑
i
n
=
1
m
d
j
j
k
n
(
i
1
i
2
i
3
⋯
i
n
)
k
d^{kn}\sum_{j=1}^{\frac{m}{d}}\mu(j)\sum_{i_1=1}^{\frac{m}{dj}}\sum_{i_2=1}^{\frac{m}{dj}}\sum_{i_3=1}^{\frac{m}{dj}}\cdots\sum_{i_n=1}^{\frac{m}{dj}}j^{kn}(i_1i_2i_3\cdots i_n)^k
dknj=1∑dmμ(j)i1=1∑djmi2=1∑djmi3=1∑djm⋯in=1∑djmjkn(i1i2i3⋯in)k
d
k
n
∑
j
=
1
m
d
μ
(
j
)
j
k
n
∑
i
1
=
1
m
d
j
∑
i
2
=
1
m
d
j
∑
i
3
=
1
m
d
j
⋯
∑
i
n
=
1
m
d
j
(
i
1
i
2
i
3
⋯
i
n
)
k
d^{kn}\sum_{j=1}^{\frac{m}{d}}\mu(j)j^{kn}\sum_{i_1=1}^{\frac{m}{dj}}\sum_{i_2=1}^{\frac{m}{dj}}\sum_{i_3=1}^{\frac{m}{dj}}\cdots\sum_{i_n=1}^{\frac{m}{dj}}(i_1i_2i_3\cdots i_n)^k
dknj=1∑dmμ(j)jkni1=1∑djmi2=1∑djmi3=1∑djm⋯in=1∑djm(i1i2i3⋯in)k
乘积展开可以为k次幂的和，只要预处理小于m的k次幂和就可以做了
d
k
n
∑
j
=
1
m
d
μ
(
j
)
j
k
n
(
1
k
+
2
k
+
3
k
+
⋯
+
(
m
d
j
)
k
)
n
d^{kn}\sum_{j=1}^{\frac{m}{d}}\mu(j)j^{kn}(1^k+2^k+3^k+\cdots+(\frac{m}{dj})^k)^n
dknj=1∑dmμ(j)jkn(1k+2k+3k+⋯+(djm)k)n
n比较大，用欧拉降幂
#include <bits/stdc++.h>
using namespace std;
const int N=1e5+5;
const int mod=59964251;
const int phi=59870352;
int mu[N];
int prime[N];
int vis[N];
int cnt;
long long sum[N];
char str[N];
void init()
{
mu[1]=1;
for(int i=2; i<N; i++)
{
if(!vis[i])
{
prime[cnt++]=i;
mu[i]=-1;
}
for(int j=0; j<cnt&&i*prime[j]<N; j++)
{
vis[prime[j]*i]=1;
if(i%prime[j]==0)
{
mu[i*prime[j]]=0;
break;
}
else
mu[i*prime[j]]=-mu[i];
}
}
}
long long quickmod(long long a,long long b)
{
long long ans=1;
while(b)
{
if(b%2==1)
ans=ans*a%mod;
b=b/2;
a=a*a%mod;
}
return ans;
}
int main()
{
init();
int t;
scanf("%d",&t);
while(t--)
{
long long m,d,k;
scanf("%s%lld%lld%lld",str,&m,&d,&k);
m/=d;
sum[0]=0;
for(int i=1; i<=m; i++)
sum[i]=(sum[i-1]+quickmod(i,k))%mod;
int len=strlen(str);
int flag=0;
long long n=0;
for(int i=0; i<len; i++)
{
n=n*10+str[i]-'0';
n=n%phi;
}
long long ans=0;
for(int i=1; i<=m; i++)
{
ans=(ans+mu[i]*quickmod(i,k*n%phi+phi)%mod*quickmod(sum[m/i],n+phi)%mod+mod)%mod;
}
ans=ans*quickmod(d,k*n%phi+phi)%mod;
printf("%lld\n",ans);
}
return 0;
}
/*
59870352
*/
/*
1
1000000000 100000 100000 1000000000
38069446
*/
