记录编号	357774	评测结果	AAAAAAAAAA
题目名称	[BZOJ 4407] 于神之怒加强版	最终得分	100
用户昵称	sxysxy	是否通过	通过
代码语言	C++	运行时间	9.226 s
提交时间	2016-12-12 17:41:47	内存使用	109.99 MiB

#include <cstdio>
#include <cstring>
#include <cstdarg>
#include <iostream>
#include <queue>
#include <vector>
#include <list>
using namespace std;
#define MAXN 5000001
#define MOD 1000000007
typedef long long LL;
int miu[MAXN];
bool vis[MAXN];
int primes[MAXN/2], tot;
LL pw[MAXN];
LL g[MAXN];
LL pow_mod(LL base, LL exp)
{
    LL ans = 1;
    for(base %= MOD; exp; base=base*base%MOD, exp >>= 1)
        if(exp&1)ans = ans*base%MOD;
    return ans;
}
void pre(int n, int k)
{
    miu[1] = 1;
    pw[1] = g[1] = 1;
    for(int i = 2; i <= n; i++)
    {
        if(!vis[i])
        {
            primes[tot++] = i;
            miu[i] = -1;
            pw[i] = pow_mod(i, k);
            g[i] = (pw[i]+MOD-1)%MOD;
        }
        for(int j = 0; j < tot; j++)
        {
            int k = primes[j]*i;
            if(k > n)break;
            vis[k] = true;
            pw[k] = pw[i]*pw[primes[j]]%MOD;
            if(i%primes[j])
            {
                miu[k] = -miu[i];
                g[k] = g[i]*g[primes[j]]%MOD;
            }else
            {
                g[k] = pw[primes[j]]*g[i]%MOD;
                break;
            }
        }
    }
    for(int i = 2; i <= n; i++)g[i] = (g[i]+g[i-1])%MOD;
}
int main()
{
    freopen("bzoj_4407.in", "r", stdin);
    freopen("bzoj_4407.out", "w", stdout);
    int T, k;
    scanf("%d %d", &T, &k);
    pre(5000000, k);
    while(T--)
    {
        LL n, m;
        scanf("%lld%lld", &n, &m);
        LL ans = 0;
        if(n > m)swap(n, m);
        for(int i = 1, j; i <= n; i = j+1)
        {
            j = min(n/(n/i), m/(m/i));
            ans = (ans+((LL)(n/i)*(LL)(m/i)%MOD)*((g[j]-g[i-1]+MOD)%MOD)%MOD)%MOD;
        }
        printf("%lld\n", ans);
    }        
    return 0;
}