LibreOJ 2000 「SDOI2017」数字表格

Very obviously, 题目让我们求 n∏i=1m∏j=1fgcd(i,j)。
按照套路，我们枚举 gcd，转化为求 min(n,m)∏i=1fin∑x=1m∑y=1[gcd(x,y)=i]。

把指数那个式子拉出来单独讨论。
根据套路，有 n∑x=1m∑y=1[gcd(x,y)=i]=∑i|dμ(di)⌊nd⌋⌊md⌋=∑id≤min(n,m)μ(d)⌊nid⌋⌊mid⌋

那么 min(n,m)∏i=1fin∑x=1m∑y=1[gcd(x,y)=i]=min(n,m)∏i=1fi∑id≤min(n,m)μ(d)⌊nid⌋⌊mid⌋=min(n,m)∏i=1∏d|ifdμ(id)⌊ni⌋⌊mi⌋=min(n,m)∏i=1(∏d|ifdμ(id))⌊ni⌋⌊mi⌋

显然外层的指数可以数论分块，内层这个东西好像不太可做……
那就暴力预处理前缀积啊，反正枚举倍数 O(nlogn)！

另外此题超卡常，请全开 int 并预处理前缀积的逆元。

代码：

#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 1e6;
const int mod = 1e9 + 7;
int t;
int cnt,prime[N + 5],vis[N + 5],mu[N + 5];
int f[N + 5],g[N + 5],prod[N + 5],inv[N + 5],ans;
int fpow(int a,int b)
{
    int ret = 1;
    for(;b;b >>= 1)
    {
        if(b & 1)
            ret = (long long)ret * a % mod;
        a = (long long)a * a % mod;
    }
    return ret;
}
int main()
{
    f[1] = g[1] = mu[1] = prod[0] = inv[0] = prod[1] = inv[1] = 1;
    for(register int i = 2;i <= N;++i)
    {
        prod[i] = 1,f[i] = (f[i - 1] + f[i - 2]) % mod,g[i] = fpow(f[i],mod - 2);
        if(!vis[i])
            prime[++cnt] = i,mu[i] = -1;
        for(register int j = 1;j <= cnt && i * prime[j] <= N;++j)
        {
            vis[i * prime[j]] = 1;
            if(!(i % prime[j]))
                break;
            mu[i * prime[j]] = -mu[i];
        }
    }
    for(register int i = 1;i <= N;++i)
        if(mu[i])
            for(register int j = 1;i * j <= N;++j)
                prod[i * j] = (long long)prod[i * j] * (mu[i] == 1 ? f[j] : g[j]) % mod;
    for(register int i = 1;i <= N;++i)
        prod[i] = (long long)prod[i] * prod[i - 1] % mod,inv[i] = fpow(prod[i],mod - 2);
    scanf("%d",&t);
    int n,m;
    while(t--)
    {
        ans = 1;
        scanf("%d%d",&n,&m);
        if(n > m)
            swap(n,m);
        for(register int l = 1,r;l <= n;l = r + 1)
        {
            r = min(n / (n / l),m / (m / l));
            ans = (long long)ans * fpow((long long)prod[r] * inv[l - 1] % mod,(long long)(n / l) * (m / l) % (mod - 1)) % mod;
        }
        printf("%d\n",ans);
    }
}