题目
题目描述
给定n,m,k,计算
$\sum_{i=1}^n \sum_{j=1}^m \gcd(i,j)^k$
对1000000007取模的结果
输入输出格式
输入格式：
多组数据。 第一行是两个数T,K; 之后的T行，每行两个整数n，m；
输出格式：
K行，每行一个结果
输入输出样例
输入样例#1：
1 2
3 3
输出样例#1：
20
说明
T<=2000,1<=N,M,K<=5000000
题解
题目要求：$\sum_{i=1}^n \sum_{j=1}^m \gcd(i,j)^k$
化简：$\sum_{d=1}^{min(n,m)}\sum_{i=1}^{n}\sum_{j=1}^{m}[\gcd(i,j)==d]d^k$
可以把$d$提到前面去：$\sum_{d=1}^{min(n,m)}d^k\sum_{i=1}^{n}\sum_{j=1}^{m}[\gcd(i,j)==d]$
后面这堆是不是很熟悉？$\sum_{d=1}^{min(n,m)}d^k\sum_{d\vert T}\mu(\frac{T}{d})\left\lfloor\frac{n}{T}\right\rfloor\left\lfloor\frac{m}{T}\right\rfloor$
枚举$T$：$\sum_{T=1}^{min(n,m)}\left\lfloor\frac{n}{T}\right\rfloor\left\lfloor\frac{m}{T}\right\rfloor\sum_{d\vert T}\mu(\frac{T}{d})d^k$
这个式子就可以用整除分块优化了
代码
# include<iostream>
# include<cstring>
# include<cstdio>
# include<algorithm>
# define LL long long
using namespace std;
const int MAX=5e6+1,mod=1e9+7;
int T,k,n,m,tot,maxn;
int dk[MAX],pm[MAX];
LL A[MAX];
int qu[MAX][2];
bool use[MAX];
LL pow(LL a,LL b)
{
LL ans=1;
for(;b;b>>=1,a=a*a%mod)
if(b&1) ans=ans*a%mod;
return ans;
}
int main()
{
scanf("%d%d",&T,&k);
for(int i=1;i<=T;++i)
scanf("%d%d",&qu[i][0],&qu[i][1]),maxn=max(maxn,min(qu[i][0],qu[i][1]));
dk[1]=1,A[1]=1;
for(int i=2;i<=maxn;++i)
{
if(!use[i]) pm[++tot]=i,dk[tot]=pow(i,k),A[i]=dk[tot]-1;
for(int j=1;j<=tot&&pm[j]*i<=maxn;++j)
{
use[i*pm[j]]=1;
if(i%pm[j]==0)
{
A[i*pm[j]]=1ll*A[i]*dk[j]%mod;
break;
}
A[i*pm[j]]=A[i]*A[pm[j]]%mod;
}
}
for(int i=1;i<=maxn;++i)
A[i]=(A[i]+A[i-1])%mod;
for(int i=1;i<=T;++i)
{
n=qu[i][0],m=qu[i][1];
if(n>m) swap(n,m);
LL ans=0;
for(int l=1,r;l<=n;l=r+1)
r=min(n/(n/l),m/(m/l)),ans=(ans+1ll*(n/l)*(m/l)%mod*(A[r]-A[l-1])%mod)%mod;
printf("%lld\n",ans>=0?ans:(ans+mod));
}
return 0;
}
本来我写的bzoj TLE了bzoj老爷机真™慢，在线筛过程中一步求出$\sum_{d\vert T}\mu(\frac{T}{d})d^k$就好了qwq
