记录编号	230836	评测结果	AAAAAAAAAA
题目名称	[BZOJ 4407] 于神之怒加强版	最终得分	100
用户昵称	stdafx.h	是否通过	通过
代码语言	C++	运行时间	6.836 s
提交时间	2016-02-24 12:04:24	内存使用	26.01 MiB

#define maxn 5000002ul

#include <stdio.h>

int sum[maxn],T,cnt,K,prime[maxn>>3],ksm_ret[maxn>>3];
bool isp[maxn];
const int mod=1e9+7;

int ksm(int p,int k){
	int ans=1;
	while(k){
		if(k&1) ans=(1ll*ans*p)%mod;
		k>>=1,p=(1ll*p*p)%mod;
	}
	return ans;
}

int Min(int a,int b){
	return a<b?a:b;
}

int work(int n,int m){
	int ans=0;
	if(n>m) n^=m,m^=n,n^=m;
	for(int i=1,last;i<=n;i=last+1){
		last=Min(n/(n/i),m/(m/i));
		(ans+=(1ll*(sum[last]-sum[i-1])*(1ll*(n/i)*(m/i)%mod))%mod)%=mod;
	}
	return (ans%mod+mod)%mod;
}

int main(){
	freopen("bzoj_4407.in","r",stdin);
	freopen("bzoj_4407.out","w",stdout);
	scanf("%d%d",&T,&K),sum[1]=1;
	for(int i=2;i<maxn;i++){
		if(!isp[i]) prime[++cnt]=i,sum[i]=ksm_ret[cnt]=ksm(i,K),sum[i]--;
		for(int j=1,x;j<=cnt&&i*prime[j]<maxn;j++){
			x=i*prime[j],isp[x]=true;
			if(i%prime[j]) sum[x]=(1ll*sum[i]*ksm_ret[j]-sum[i])%mod;
			else{sum[x]=(1ll*sum[i]*ksm_ret[j])%mod;break;}
		}
		(sum[i]+=sum[i-1])%=mod;
	}
	for(int i=1,a,b;i<=T;i++){
		scanf("%d%d",&a,&b);
		printf("%d\n",work(a,b));
	}
	return 0;
}