[SDOI2017]数字表格

这题其实并不难啊,有个结论比较显然

下面推个狮子

#include <bits/stdc++.h>

using namespace std;

typedef long long LLL;

const int N = 1e6 + 10, mod = 1e9 + 7, Mod = mod - 1;

LLL prime[N], mu[N], Fib[N], phi[N], inv_Fib[N], f[N], cnt;

bool st[N];

LLL quick_pow(LLL a, int n) {
  LLL res = 1;
  while(n) {
    if(n & 1) res = res * a % mod;
    a = a * a % mod;
    n >>= 1;
  }
  return res;
}

LLL inv(LLL a) {
  return quick_pow(a, mod - 2);
}

void init() {
      Fib[1] = mu[1] = f[1] = 1;
      for(int i = 2; i < N; i++)
      {
        f[i] = 1;
        Fib[i] = (Fib[i - 1] + Fib[i - 2]) % mod;
        if(!st[i]) {
          prime[++cnt] = i;
          mu[i] = -1;
        }
        for(int j = 1; j <= cnt && 1ll * i * prime[j] < N; j++) 
        {
          st[i * prime[j]] = 1;
          if(i % prime[j] == 0)     break;
          mu[i * prime[j]] = -mu[i];
        }
      }
    for(int i = 1; i < N; i++)   inv_Fib[i] = inv(Fib[i]);
    for(int i = 1; i < N; i++) 
    {
        for(int j = i; j < N; j += i) 
        {
          if(mu[j / i] == 1) 
            f[j] = f[j] * Fib[i] % mod;
          else if(mu[j / i] == -1)
            f[j] = f[j] * inv_Fib[i] % mod;
        }
      }
  f[0] = 1;
  for(int i = 1; i < N; i++) 
    f[i] = f[i] * f[i - 1] % mod;
}

int main() 
{
    init();
    int T;
    scanf("%d", &T);
      while(T--) 
   {
        int n, m;
        scanf("%d %d", &n, &m);
        if(n > m) swap(n, m);
        LLL res = 1;
        for(int l = 1, r; l <= n; l = r + 1) 
        {
            r = min(n / (n / l), m / (m / l));
            res = res * quick_pow(f[r] * inv(f[l - 1]) % mod, 1ll * (n / l) * (m / l) % Mod) % mod;
        }
        printf("%lld\n", res);
   }
  return 0;
}