题意
给出n,m,k求
![](https://img.laitimes.com/img/9ZDMuAjOiMmIsIjOiQnIsICdzFWRoRXdvN1LclHdpZXYyd2LcBzNvwVZ2x2bzNXak9CX90TQNNkRrFlQKBTSvwFbslmZvwFMwQzLcVmepNHdu9mZvwFVywUNMZTY18CX052bm9CX9klaOBzaq1UeNpXTmZEWjZXUYpVd1kmYr50MZV3YyI2cKJDT29GRjBjUIF2LcRHelR3LcJzLctmch1mclRXY39DNzUDMygjMxEDMyEDM3EDMy8CX0Vmbu4GZzNmLn9Gbi1yZtl2Lc9CX6MHc0RHaiojIsJye.jpg)
多组数据
n,m<=5000000,T<=2000
分析
设d=gcd(i,j)
那么ans=∑nd=1dk∗f(d)
f(d)表示1<=i<=n,1<=j<=m中gcd(i,j)=d的(i,j)对数
反演后可得ans=∑nd=1dk∑⌊nd⌋i=1μ(i)⌊ndi⌋⌊mdi⌋
设T=di则ans=∑nT=1⌊nT⌋⌊mt⌋∑d|Tdkμ(Td)
那么只要求出∑d|Tdkμ(Td)的前缀和即可O(n√)询问
设f(d)=dk,g(d)=μ(d),h(T)=∑d|Tf(d)g(Td)
显然h为f和g的狄利克雷卷积,因为f和g均为积性函数,那么h也为积性函数,那么就可以用线性筛来求出h
low[i]表示i的最小质因子的其对应指数的次方。
代码
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#define N 5000005
#define ll long long
using namespace std;
const int MOD=;
int k,n,m,tot,prime[N],low[N],f[N];
bool not_prime[N];
int ksm(int x,int y)
{
if (!y) return ;
if (y==) return x;
int w=ksm(x,y/);
w=(ll)w*w%MOD;
if (y%==) w=(ll)w*x%MOD;
return w;
}
void prework(int n)
{
f[]=;
for (int i=;i<=n;i++)
{
if (!not_prime[i])
{
low[i]=prime[++tot]=i;
f[i]=ksm(i,k)-;
}
for (int j=;j<=tot&&i*prime[j]<=n;j++)
{
not_prime[i*prime[j]]=;
if (i%prime[j]==)
{
if (low[i]==i) f[i*prime[j]]=(ll)f[i]*(f[prime[j]]+)%MOD;
else f[i*prime[j]]=(ll)f[low[i]*prime[j]]*f[i/low[i]]%MOD;
low[i*prime[j]]=low[i]*prime[j];
break;
}
f[i*prime[j]]=(ll)f[i]*f[prime[j]]%MOD;
low[i*prime[j]]=prime[j];
}
}
for (int i=;i<=n;i++)
f[i]=(f[i-]+f[i])%MOD;
}
int main()
{
int t;
scanf("%d%d",&t,&k);
prework();
while (t--)
{
scanf("%d%d",&n,&m);
if (n>m) swap(n,m);
int ans=;
for (int i=,last;i<=n;i=last+)
{
last=min(n/(n/i),m/(m/i));
ans=(ans+(ll)(n/i)*(m/i)%MOD*(f[last]-f[i-])%MOD)%MOD;
}
printf("%d\n",(ans+MOD)%MOD);
}
return ;
}