记录编号	379688	评测结果	AAAAAAAAAA
题目名称	[BZOJ 4407] 于神之怒加强版	最终得分	100
用户昵称	Go灬Fire	是否通过	通过
代码语言	C++	运行时间	4.190 s
提交时间	2017-03-07 13:52:43	内存使用	173.41 MiB

#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define LL long long
#define Inf 2e9
const int mod=1e9+7;
const int maxn=5500000;
int till,K;
int Prime[maxn],tot,h[maxn];
LL sum[maxn],g[maxn];
bool vis[maxn];
int qpow(int x,int h){
	int ans=1;
	while(h){
		if(h&1)ans=1ll*ans%mod*1ll*x%mod;
		x=1ll*x%mod*1ll*x%mod;h>>=1;
	}
	return ans;
}
void Pre(){
	g[1]=1;
	for(int i=2;i<=till;i++){
		if(!vis[i]){
			Prime[++tot]=i;
			h[i]=qpow(i,K);
			g[i]=h[i]-1;if(g[i]<0)g[i]+=mod;
		}
		for(int j=1;j<=tot && i*Prime[j]<=till;j++){
			vis[i*Prime[j]]=true;
			if(i%Prime[j]==0){
				g[i*Prime[j]]=1ll*g[i]%mod*1ll*h[Prime[j]]%mod;
				break;
			}
			g[i*Prime[j]]=1ll*g[i]%mod*1ll*g[Prime[j]]%mod;
		}
	}
	for(int i=1;i<=till;i++)sum[i]=1ll*(sum[i-1]+g[i])%mod;
}
struct Ques{
	int n,m;
}q[maxn];
void Solve(int,int);
int main(){
	freopen("bzoj_4407.in","r",stdin);freopen("bzoj_4407.out","w",stdout);
	int T=0;scanf("%d%d",&T,&K);
	for(int i=1;i<=T;i++){
		scanf("%d%d",&q[i].n,&q[i].m);
		if(q[i].n>q[i].m)swap(q[i].n,q[i].m);
		till=max(till,q[i].n);
	}till+=500;
	Pre();
	for(int i=1;i<=T;i++)Solve(q[i].n,q[i].m);
	return 0;
}
void Solve(int n,int m){
	LL ans=0;int Next;
	for(int i=1;i<=n;i=Next+1){
		Next=min(n/(n/i),m/(m/i));
		ans+=1ll*(n/i)%mod*1ll*(m/i)%mod*1ll*(sum[Next]-sum[i-1])%mod;
		ans%=mod;
		if(ans<0)ans+=mod;
	}
	printf("%lld\n",ans);
}
/*
1 4
7 5
*/
/*
1 5
3 10
 */
/*
5 5000000
5000000 5000000
5000000 5000000
5000000 5000000
5000000 5000000
5000000 5000000
 */