记录编号	601034	评测结果	AAAAAAAAAA
题目名称	2156.[BZOJ 4407] 于神之怒加强版	最终得分	100
用户昵称	djyqjy	是否通过	通过
代码语言	C++	运行时间	3.515 s
提交时间	2025-05-24 16:05:21	内存使用	87.50 MiB

#include<bits/stdc++.h>
#define int long long
using namespace std;
inline int re()
{
    int f=1,num=0;
    char c=getchar();
    while(c<'0'||c>'9'){if(c=='-') f=-1;c=getchar();}
    while(c>='0'&&c<='9') num=num*10+c-'0',c=getchar();
    return num*f;
}
const int N=5000010,MOD=1e9+7;
int T,k,n,m,ans;
bool mark[N];
int prime[N],f[N],jsq;
int ppow[N];
int qpow(int a,int b)
{
    int mul=1;
    for(;b;b>>=1,a=a*a%MOD) if(b&1) mul=mul*a%MOD;
    return mul;
}
void init()
{
    mark[1]=f[1]=1;
    for(int i=2;i+10<=N;i++)
    {
        if(!mark[i]) prime[++jsq]=i,ppow[i]=qpow(i,k),f[i]=ppow[i]-1;
        for(int j=1;j<=jsq;j++)
        {
            if(i*prime[j]+10>N) break;
            mark[i*prime[j]]=1;
            if(i%prime[j]==0)
            {
                f[i*prime[j]]=f[i]*ppow[prime[j]]%MOD;
                break;
            }
            f[i*prime[j]]=f[i]*(ppow[prime[j]]-1)%MOD;
        }
    }
    for(int i=2;i+10<=N;i++) f[i]=(f[i]+f[i-1])%MOD;
    return;
}
signed main()
{
    freopen("bzoj_4407.in","r",stdin);
    freopen("bzoj_4407.out","w",stdout);
    T=re();k=re();init();
    while(T--)
    {
        n=re();m=re();
        if(n>m) swap(n,m);
        for(int l=1,r=0;l<=n;l=r+1)
        {
            r=min(n/(n/l),m/(m/l));
            ans=(ans+(f[r]-f[l-1])*(n/l)%MOD*(m/l))%MOD;
        }
        printf("%lld\n",(ans+MOD)%MOD);
        ans=0;
    }
    return 0;
}