题目描述
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

题目分析

---

令


线性筛出 分块求解

#include <cstdio>
#include <cstring>
#include <set>
#include <map>
#include <vector>
#include <cmath>
#include <queue>
#include <algorithm>
using namespace std;
int n,m,t;
long long mod=1000000007;
long long k;
long long ksm(int tmp,long long y)
{
    long long x=tmp;
    long long sum=1;
    while(y)
    {
        if(y&1) sum=(sum*x)%mod;
        y>>=1;
        x=(x*x)%mod; 
    }
    return sum;
}
int mu[5000010],prime[5000010];
long long po[5000010],f[5000010];
bool vis[5000010];
void init()
{
    mu[1]=1;
    f[1]=1;
    for(int i=2;i<=5000000;i++)
    {
        if(!vis[i])
        {
            prime[++prime[0]]=i;
            mu[i]=-1;
            po[i]=ksm(i,k)%mod;
            f[i]=(po[i]-1+mod)%mod;
        }
        for(int j=1;j<=prime[0]&&i*prime[j]<=5000000;j++)
        {
            vis[i*prime[j]]=1;
            if(i%prime[j])
            {
                mu[i*prime[j]]=-mu[i];
                f[i*prime[j]]=(f[i]*f[prime[j]])%mod;
            }
            else
            {
                f[i*prime[j]]=(f[i]*po[prime[j]])%mod;
                break;
            }
        }
    }
    for(int i=1;i<=5000000;i++) f[i]=(f[i-1]+f[i])%mod;
}
void work(int x,int y)
{
    if(x>y) swap(x,y);
    int last=0;
    long long ans=0;
    for(int i=1;i<=x;i=last+1)
    {
        last=min(x/(x/i),y/(y/i));
        ans=(ans+(((long long)(x/i)*(y/i))%mod)*((f[last]-f[i-1])%mod+mod)%mod)%mod;
    }
    printf("%lld\n",ans);
}
int main()
{   
    scanf("%d%lld",&t,&k);
    init();
    while(t--) scanf("%d%d",&n,&m),work(n,m);
    return 0;
}