【题解】[SDOI2017] 数字表格 BZOJ – 4816

题目链接_(:зゝ∠)_

本题要求：

$$\prod _ {i = 1} ^ n \prod _ {j = 1} ^ m f _ {gcd(i, j)}$$

其中 $f _ i$表示斐波那契数列第 $i$项

（其实可以把问题出成 $gcd(f _ i, f _ j)$，这样还得多一个套路嘿嘿嘿）

于是就推柿子：

$$
\begin{equation}
\begin{aligned}
&\prod _ {i = 1} ^ n \prod _ {j = 1} ^ m f _ {gcd(i, j)}\\
=&\prod _ {d = 1} ^ n \prod _ {i = 1} ^ n \prod _ {j = 1} ^ m [gcd(i, j) = d] \times f _ d\\
=&\prod _ {d = 1} ^ n f _ d ^ {\sum _ {i = 1} ^ {\lfloor \frac n d \rfloor} \sum _ {j = 1} ^ {\lfloor \frac m d \rfloor} [gcd(i, j) == 1]}
\end{aligned}
\end{equation}
$$

康康指数：

$$
\begin{equation}
\begin{aligned}
&\sum _ {i = 1} ^ {\lfloor \frac n d \rfloor} \sum _ {j = 1} ^ {\lfloor \frac m d \rfloor} [gcd(i, j) == 1]\\
=&\sum _ {t = 1} ^ {\lfloor \frac n d \rfloor} \mu(t) \lfloor \frac n {dt} \rfloor \lfloor \frac m {dt} \rfloor
\end{aligned}
\end{equation}
$$

设 $T = dt$，先枚举 $T$，放到原式中：

$$
\begin{equation}
\begin{aligned}
&\prod _ {T = 1} ^ n \prod _ {d | T} f _ d ^ {\mu(\frac T d) \lfloor \frac n T \rfloor \lfloor \frac m T \rfloor}\\
=&\prod _ {T = 1} ^ n (\prod _ {d | T} f _ d ^ {\mu(\frac T d)}) ^ {\lfloor \frac n T \rfloor \lfloor \frac m T \rfloor}
\end{aligned}
\end{equation}
$$

于是就外层除法分块，内层暴力预处理就行了

代码：

#include <bits/stdc++.h>

#define NS (1000001)
#define MOD (1000000007)
#define pls(a, b) ((a) + (b) < MOD ? (a) + (b) : (a) + (b) - MOD)
#define mns(a, b) ((a) - (b) < 0 ? (a) - (b) + MOD : (a) - (b))
#define mul(a, b) (1ll * (a) * (b) % MOD)
#define Inv(a) (qpow((a), MOD - 2))

using namespace std;

template<typename _Tp> inline void IN(_Tp& dig)
{
    char c; bool flag = 0; dig = 0;
    while (c = getchar(), !isdigit(c)) if (c == '-') flag = 1;
    while (isdigit(c)) dig = dig * 10 + c - '0', c = getchar();
    if (flag) dig = -dig;
}

int qpow(int a, int b)
{
    int res = 1;
    while (b)
    {
        if (b & 1) res = mul(res, a);
        a = mul(a, a), b >>= 1;
    }
    return res;
}

int testcase, n, m, p[NS], cnt, mu[NS], f[NS], g[NS], ng[NS], ans;

bool vis[NS];

void preWork()
{
    mu[1] = f[1] = 1;
    for (int i = 2; i < NS; i += 1)
    {
        f[i] = pls(f[i - 1], f[i - 2]);
        if (!vis[i]) p[++cnt] = i, mu[i] = -1;
        for (int j = 1; j <= cnt; j += 1)
        {
            int k = i * p[j];
            if (k >= NS) break;
            vis[k] = 1, mu[k] = -mu[i];
            if (i % p[j] == 0) { mu[k] = 0; break; }
        }
    }
    fill(g, g + NS, 1), fill(ng, ng + NS, 1);
    for (int i = 1; i < NS; i += 1)
    {
        int iv = Inv(f[i]);
        for (int j = i; j < NS; j += i)
        {
            if (!mu[j / i]) continue;
            if (mu[j / i] > 0) g[j] = mul(g[j], f[i]), ng[j] = mul(ng[j], iv);
            else g[j] = mul(g[j], iv), ng[j] = mul(ng[j], f[i]);
        }
    }
    for (int i = 1; i < NS; i += 1)
        g[i] = mul(g[i], g[i - 1]), ng[i] = mul(ng[i], ng[i - 1]);
}

int main(int argc, char const* argv[])
{
    IN(testcase), preWork();
    while (testcase--)
    {
        IN(n), IN(m), ans = 1;
        if (n > m) swap(n, m);
        for (int l = 1, r; l <= n; l = r + 1)
        {
            r = min(n / (n / l), m / (m / l));
            int x = mul(g[r], ng[l - 1]);
            ans = mul(ans, qpow(qpow(x, n / l), m / l));
        }
        printf("%d\n", ans);
    }
    return 0;
}