BZOJ傳送門
Time Limit: 80 Sec Memory Limit: 512 MB
Submit: 195 Solved: 94
[Submit][Status][Discuss]
Description
給下N,M,K.求
Input
輸入有多組資料,輸入資料的第一行兩個正整數T,K,代表有T組資料,K的意義如上所示,下面第二行到第T+1行,每行為兩個正整數N,M,其意義如上式所示。
Output
如題
Sample Input
1 2
3 3
Sample Output
20
HINT
1<=N,M,K<=5000000,1<=T<=2000
Source
命題人:成都七中張耀楠,鳴謝excited上傳。
#include<cstdio>
#include<iostream>
using namespace std;
#define N 5000010
#define P 1000000007
#define min(a,b) a>b?b:a
inline int in(int x=,char ch=getchar(),int v=){
while(ch!='-'&&(ch>'9'||ch<'0')) ch=getchar();if(ch=='-') v=-,ch=getchar();
while(ch>='0'&&ch<='9') x=(x<<)+(x<<)+ch-'0',ch=getchar();return x*v;}
int f[N],pr[N],pw[N];bool b[N];
int cnt,n,m,k,t,ans;
inline int Pow(int a,int b,int res=){while(b){if(b&) res=(long long)res*a%P;a=(long long)a*a%P,b>>=;}return res;}
inline void GetMu(){
f[]=;
for(int i=;i<N;i++){
if(!b[i]) pr[cnt]=i,pw[cnt]=Pow(i,k),f[i]=pw[cnt]-,cnt++;
for(int j=;j<cnt&&i*pr[j]<N;j++){
b[i*pr[j]]=;
if(!(i%pr[j])){f[i*pr[j]]=(long long)f[i]*pw[j]%P;break;}
f[i*pr[j]]=(long long)f[i]*f[pr[j]]%P;
}
}
for(int i=;i<N;i++)f[i]=(f[i]+f[i-])%P;
}
int main(){
t=in(),k=in();GetMu();
while(t--){
n=in(),m=in();if(n>m) swap(n,m);ans=;
for(int i=,j=;i<=n;i=j+){
j=min(n/(n/i),m/(m/i));
ans=((long long)(f[j]-f[i-]+P)*(n/i)%P*(m/i)%P+ans)%P;
}
printf("%d\n",ans);
}
return ;
}