P3704 [SDOI2017]数字表格

P3704 [SDOI2017]数字表格

$$
\begin {aligned}
ANS & = \prod _ {i = 1} ^ n \prod _ {j = 1} ^ m f _ {(i, j)} \\
& = \prod _ {d = 1} ^ n f _ d ^ {\sum _ {i = 1} ^ n \sum _ {j = 1} ^ m [(i, j) = d]} \\
\end {aligned}
$$
对于指数部分：
$$
\begin {aligned}
\sum _ {i = 1} ^ n \sum _ {j = 1} ^ m [(i, j) = d] & = \sum _ {i = 1} ^ {\lfloor \frac n d \rfloor} \sum _ {j = 1} ^ {\lfloor \frac m d \rfloor}[(i, j) = 1] \\
& = \sum _ {i = 1} ^ {\lfloor \frac n d \rfloor} \sum _ {j = 1} ^ {\lfloor \frac m d \rfloor}\sum _ {e | (i, j)} \mu(e) \\
& = \sum _ {e = 1} ^ n \mu(e) \sum _ {i = 1} ^ {\lfloor \frac n {de} \rfloor} \sum _ {j = 1} ^ {\lfloor \frac m {de} \rfloor}\\
\end {aligned}
$$
令 $T = de$ ，那么有：
$$
\begin {aligned}
ANS & = \prod _ {d = 1} ^ n f _ d ^ {\sum _ {e = 1} ^ n \mu(e) \sum _ {i = 1} ^ {\lfloor \frac n {de} \rfloor} \sum _ {j = 1} ^ {\lfloor \frac m {de} \rfloor}} \\
& = \prod _ {T = 1} ^ n \prod _ {d | T} f _ d ^ {\mu(\frac T d) \sum _ {i = 1} ^ {\lfloor \frac n T \rfloor} \sum _ {i = 1} ^ {\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}
$$
预处理 $\prod _ {d | T} f _ d ^ {\mu(\frac T d)}$ 的前缀和，数论分块。

查看代码

#include <cstdio>
#include <algorithm>
using namespace std;
template <class Type>
void read(Type &x)
{
    char c;
    bool flag = false;
    while ((c = getchar()) < '0' || c > '9')
        c == '-' && (flag = true);
    x = c - '0';
    while ((c = getchar()) >= '0' && c <= '9')
        x = (x << 3) + (x << 1) + c - '0';
    if (flag) x = ~x + 1;
}
template <class Type, class ...rest>
void read(Type &x, rest &...y) { read(x), read(y...); }
template <class Type>
void write(Type x)
{
    if (x < 0) putchar('-'), x = ~x + 1;
    if (x > 9) write(x / 10);
    putchar(x % 10 + '0');
}
typedef long long LL;
const int N = 1e6 + 10, mod = 1e9 + 7;
bool vis[N];
int n, m;
int cnt, p[N], mu[N], f[N];
int binpow (int b, int k = mod - 2)
{
    int res = 1;
    for (; k; k >>= 1, b = (LL)b * b % mod)
        if (k & 1) res = (LL)res * b % mod;
    return res;
}
void init ()
{
    vis[1] = true;
    mu[1] = 1;
    for (int i = 2; i < N; ++i)
    {
        if (!vis[i]) mu[p[++cnt] = i] = -1;
        for (int j = 1; j <= cnt && i * p[j] < N; ++j)
        {
            vis[i * p[j]] = true;
            if (i % p[j] == 0)
                { mu[i * p[j]] = 0; break; }
            mu[i * p[j]] = mu[i] * mu[p[j]];
        }
    }
    for (int i = 0; i < N; ++i) f[i] = 1;
    int a = 0, b = 1;
    for (int i = 1; i < N; ++i)
    {
        int w[3] = { binpow(b), 1, b };
        for (int j = 1; i * j < N; ++j)
            f[i * j] = (LL)f[i * j] * w[mu[j] + 1] % mod;
        (a += b) %= mod; swap(a, b);
    }
    for (int i = 2; i < N; ++i)
        f[i] = (LL)f[i - 1] * f[i] % mod;
}
int main ()
{
    init();
    int T; read(T);
    while (T--)
    {
        read(n, m);
        if (n > m) swap(n, m);
        int res = 1;
        for (int l = 1, r; l <= n; l = r + 1)
        {
            r = min(n / (n / l), m / (m / l));
            res = (LL)res * binpow((LL)f[r] * binpow(f[l - 1]) % mod, (LL)(n / l) * (m / l) % (mod - 1)) % mod;
        }
        write(res), puts("");
    }
    return 0;
}