记录编号	360921	评测结果	AAAAAAAAAA
题目名称	[BZOJ 4407] 于神之怒加强版	最终得分	100
用户昵称	FoolMike	是否通过	通过
代码语言	C++	运行时间	13.745 s
提交时间	2017-01-02 10:23:17	内存使用	95.60 MiB

#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long ll;
const int mod=1000000007,N=5e6+10;
int T,n,m,k,u[N],p[N],cnt;
bool isp[N];
ll Mi[N],sum[N];
ll mi(ll x,ll y){
	ll ans=1;
	for (;y;y>>=1,x=x*x%mod)	
		if (y&1) ans=ans*x%mod;
	return ans;
}
void init(){
	u[1]=sum[1]=Mi[1]=1;
	for (int i=2;i<=5e6;i++){
		if (!isp[i])
			p[++cnt]=i,u[i]=-1,sum[i]=Mi[i]=mi(i,k),sum[i]--;
		for (int j=1;j<=cnt&&i*p[j]<=5e6;j++){
			int x=i*p[j];isp[x]=1;
			if (i%p[j]) sum[x]=(sum[i]*(Mi[p[j]]-1))%mod;//不含p^2项，类似集合卷积 
				else{sum[x]=sum[i]*Mi[p[j]]%mod;break;}//含p^2项，必须拆掉 
		}
		sum[i]=(sum[i]+sum[i-1])%mod;
	}
}
int main()
{
	freopen("bzoj_4407.in","r",stdin);
	freopen("bzoj_4407.out","w",stdout);
	scanf("%d%d",&T,&k);
	init();
	while (T--){
		scanf("%d%d",&n,&m);
		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+(sum[r]-sum[l-1])*(n/l)%mod*(m/l))%mod;
		}
		printf("%lld\n",ans<0?ans+mod:ans);
	}
	return 0;
}