题解

代码解释：

• 预处理pk数组:使用快速幂计算每个数的k次幂模MOD。

• 线性筛法:同时计算每个数的最小质因子，利用积性函数性质高效计算$h(n),h(n)$表示对所有$d|n,μ(d)*(n/d)^k$的和，通过线性筛保证$O(n)$时间复杂度。

• 前缀和优化:$sum_h$数组存储h的前缀和，支持$O(1)$区间和查询。

• 数论分块:对每个测试用例，通过整除分块将枚举次数从$O(n)$降至$O(\sqrt n)$。

方法:莫比乌斯反演，线性筛，狄利克雷卷积，前缀和(稍显多余)

防抄袭代码(仅供参考):

# include <bits/stdc++.h>
typedef unsigned long long ull;

#define getchar getchar_unlocked()
#define putchar putchar_unlocked
#define psbc push_back
#define vco vector

using  namespace  std ;
const int MX=1e5;
int i,j,k;
int r(){
    int x=0,f=1;
    char c=getchar;
    while(c<'0'||c>'9'){if(c=='-') f=-1;c=getchar;}
    while(c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^(3<<4)),c=getchar;
    return x*f;
}
void w(int x){
    if(x<0) putchar('-'),x=~(x-1);
    else if(x>9) w(x/10);
    putchar(x%10+'0');
}
const int MOD = 1000000007;
const int MAX = 5000000;

int pk[MAX + 1]; // pk[d] = d^k mod MOD
int h[MAX + 1];  // h(n) = sum_{d|n} μ(d) * (n/d)^k
int sum_h[MAX + 1]; // 前缀和

// 快速幂计算a^b mod MOD
int qpow(int a, int b) {
    int res = 1;
    while (b) {
        if (b & 1) res = 1LL * res * a % MOD;
        a = 1LL * a * a % MOD;
        b >>= 1;
    }
    return res;
}

void precompute(int k) {
    // 预处理pk数组
    pk[1] = 1;
    for (int d = 2; d <= MAX; ++d) {
        pk[d] = qpow(d, k);
    }
    
    // 线性筛预处理h数组
    bool is_prime[MAX + 1] = {false};
    vector<int> primes;
    h[1] = 1;
    for (int i = 2; i <= MAX; ++i) {
        if (!is_prime[i]) {
            primes.push_back(i);
            h[i] = (pk[i] - 1 + MOD) % MOD; // 质数p的h(p) = p^k - 1
        }
        for (auto p : primes) {
            if (i * p > MAX) break;
            is_prime[i * p] = true;
            if (i % p == 0) {
                h[i * p] = 1LL * h[i] * pk[p] % MOD; // p是i的最小质因子，且i包含p的幂次
                break;
            }
            else {
                h[i * p] = 1LL * h[i] * h[p] % MOD; // 互质时h是积性函数
            }
        }
    }
    
    // 计算前缀和
    sum_h[0] = 0;
    for (int i = 1; i <= MAX; ++i) {
        sum_h[i] = (sum_h[i - 1] + h[i]) % MOD;
    }
}
int  main ( )
{
    int T = r(), k = r();
    precompute(k);
    while (T --) {
        int n = r(), m = r();
        if (n > m) swap(n, m); // 保证n <= m   
        int ans = 0, l = 1, r;
        while (l <= n) {
            r = min(n / (n / l), m / (m / l));
            r = min(r, n); // 确保不超过n            
            int sum = (sum_h[r] - sum_h[l - 1] + MOD) % MOD;
            int a = n / l, b = m / l;
            int term = 1LL * a * b % MOD;
            term = 1LL * term * sum % MOD;
            ans = (ans + term) % MOD;            
            l = r + 1;
        }
        w(ans);
        putchar('\n');
    }
    return  0;
}