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

#include <cstdio>
#include <vector>
#include <algorithm>
typedef long long ll;

const int MAXN = 5e6 + 10;
const int MOD = 1e9 + 7;

ll kasumi(ll x, ll y) {
  ll res = 1;
  while (y) {
    if (y & 1) res = res * x % MOD;
    y >>= 1;
    x = x * x % MOD;
  }
  return res;
}

ll k;

bool vis[MAXN];
ll f[MAXN];
::std::vector <ll> primes, mi;
void solve(ll n) {
  f[1] = 1;
  for (ll i = 2; i <= n; ++i) {
    if (!vis[i]) {
      primes.push_back(i);
      f[i] = (kasumi(i, k) - 1 + MOD) % MOD;
    }
    for (ll p : primes) {
      if (i * p > n) break;
      vis[i * p] = 1;
      if (i % p == 0) {
        f[i * p] = f[i] * kasumi(p, k) % MOD;
        break;
      } else {
        f[i * p] = f[i] * f[p] % MOD; /* kasumi(p, k) - 1*/
      }
    }
  }
  for (ll i = 1; i <= n; ++i) {
    f[i] = (f[i] + f[i - 1]) % MOD;
  }
}

int T;
ll n, m;
ll ans;

int main() {
  freopen("bzoj_4407.in", "r", stdin);
  freopen("bzoj_4407.out", "w", stdout);
  scanf("%d %lld", &T, &k);
  solve(MAXN - 10);
  while (T--) {
    scanf("%lld %lld", &n, &m);
    if (n > m) n ^= m ^= n ^= m;
    ans = 0;
    for (ll i = 1, ed; i <= n; i = ed + 1) {
      ed = ::std::min(n / (n / i), m / (m / i));
      ans = (ans + (n / i) * (m / i) % MOD * (f[ed] - f[i - 1] + MOD) % MOD) % MOD;
    }
    printf("%lld\n", ans);
  }
  return 0;
}