给下N,M,K.求
1<=N,M,K<=5000000,1<=T<=2000
思路{
把该式变成枚举gcd
Ans=(min(n,m))∑(i=1) (i^k)*F(i) F(d)=∑(1<=i<=n,,1<=j<=m)(d|gcd(i,j))
套路莫比乌斯反演得F(n)=∑(n|d)(n/d)*(m/d)*μ(d/n)
Ans=(min(n,m))∑(i=1) (i^k)* ∑(i|d)(n/d)*(m/d)*μ(d/i)
套路把(n/d)*(m/d)提前
Ans=(min(n,m)) ∑(D=1) (n/D)*(m/D)*∑(i|D) μ(D/i)*(i^k)
关键就是后面这个东东=∑(i|D) μ(D/i)*(i^k)
设G(D)=∑(i|D) μ(D/i)*(i^k).为狄利克雷卷积形式(然而我不知道有什么卵用)
然后打表发现它是一个积性函数,线性筛就可以了.
}
#include<bits/stdc++.h>
#define RG register
#define il inline
#define db double
#define LL long long
#define N 5000010
#define mod 1000000007
using namespace std;
LL p[N],k,t,n,m;bool vis[N];
LL Q[N],F[N];
LL qp(LL a,LL b){
if(!b)return 1;if(b==1)return a;
LL tmp=qp(a,(b>>1));
tmp=(tmp*tmp)%mod;
if(b&1)tmp=(tmp*a)%mod;
return tmp;
}
void make(){
F[1]=1;
for(LL i=2;i<N;++i){
if(!vis[i])p[++p[0]]=i,Q[i]=qp((LL)i,k),F[i]=(Q[i]-1+mod)%mod;
for(int j=1;j<=p[0]&&p[j]*i<N;++j){
vis[p[j]*i]=true;
if(i%p[j])F[p[j]*i]=(F[i]*F[p[j]])%mod;
else {F[p[j]*i]=(F[i]*Q[p[j]])%mod;break;}
}
}
for(int i=2;i<N;++i)F[i]+=F[i-1],F[i]%=mod;
}
void work(){
LL Ans(0);
for(LL l=1,r;l<=n;l=r+1){
r=min(n/(n/l),m/(m/l));
Ans+=(((F[r]-F[l-1]+mod)%mod)*(((LL)(n/l)*(LL)(m/l))%mod))%mod;
if(Ans>=mod)Ans-=mod;
}cout<<Ans<<"\n";
}
int main(){
scanf("%lld%lld",&t,&k);make();
while(t--){
scanf("%lld%lld",&n,&m);
if(n>m)swap(n,m);work();
}return 0;
}
原文：http://www.cnblogs.com/zzmmm/p/7487558.html