【题解】[SDOI2017] 数字表格 莫比乌斯反演 ——quhengyi11

传送喵

题目喵述

($n,m \leq 10^6$，数据组数 $T \leq 10^3$) 求

$$\prod_{i=1}^n\prod_{j=1}^m fib[gcd(i,j)]$$

其中 $fib[n]$表示斐波那契数列第 $n$项

喵解

数学题太有趣了 (破音 (雾))

首先前面一部分都是套路的东西了

很自然地想到，令
$$g(d)=\sum_{i=1}^n\sum_{j=1}^m[gcd(i,j)==d]$$

则

$$ans=\prod_{d=1}^nfib[d]^{g(d)}$$

自然地把 $g$给化简一下

$$g(d)=\sum_{i=1}^{\frac n d}\sum_{j=1}^{\frac m d}[gcd(i,j) == 1]$$

相必这个式子你已经能一口说出化简结果了

$$g(d)=\sum_{i=1}^{\frac n d} \mu(i)[\frac n {id}][\frac m {id}]$$

代回原来的式子

$$
\begin{align}
ans&=\prod_{d=1}^nfib[d]^{\sum_{i=1}^{\frac n d} \mu(i)[\frac n {id}][\frac m {id}]}\\
&=\prod_{d=1}^n\prod_{i=1}^{\frac n d} fib[d]^{\mu(i)[\frac n {id}][\frac m {id}]}
\end{align}
$$

又是熟悉的味道，令 $T=id$

$$\prod_{T=1}^n\prod_{d|T} fib[d]^{\mu(\frac n d)[\frac n T][\frac m T]}$$

你如果对时间复杂度有感觉那么你会发现已经什么都结束了

$$\prod_{T=1}^n(\prod_{d|T} fib[d]^{\mu(\frac n d)})^{[\frac n T][\frac m T]}$$

里面的东西可以 $O(nlog^2n)$计算 (有一个算逆元的 log 在里面，不过由于很多 $\mu$是 $0$或者 $1$其实总复杂度是接近 $O(nlogn)$的)

外面的东西显然数论分块，复杂度 $O(T4\sqrt n)$

感觉数学题时间都卡得刚刚好啊，我还是把常数也算里面去吧（

代码

#include<bits/stdc++.h>
#define fo(i, a, b) for (int i = (a); i <= (b); ++i)

#define mod 1000000007
#define N 1000005
#define ll long long
std::bitset<N> vis;
ll mu[N], p[N], tot, up, fib[N], pd[N];
inline ll pow (ll x, ll y = mod - 2)
{
    ll ret = 1;
    while (y)
    {
        if (y & 1) ret = ret * x % mod;
        x = x * x % mod;
        y >>= 1;
    }
    return ret;
}
inline void init ()
{
    up = N - 3;
    fib[0] = 0; fib[1] = 1; pd[0] = 1; pd[1] = 1;
    fo (i, 2, up) {fib[i] = (fib[i - 1] + fib[i - 2]) % mod; pd[i] = 1;}
    mu[1] = 1;
    fo (i, 2, up)
    {
        if (!vis[i])
            p[++tot] = i, mu[i] = -1;
        vis[i] = 1;
        for (int j = 1; j <= tot && i * p[j] <= up; ++j)
        {
            vis[i * p[j]] = 1;
            if (!(i % p[j])) {break;}
            mu[i * p[j]] = -mu[i];
        }
    }
    fo (d, 1, up)
        for (int T = d, div = 1; T <= up; T += d, ++div) // div = T / d
            if (mu[div])
                pd[T] = pd[T] * ((mu[div] == 1) ? fib[d] : pow(fib[d])) % mod;
    fo (i, 2, up)
        pd[i] = pd[i] * pd[i - 1] % mod;
}
int main()
{
    int T;
    scanf("%d", &T);
    init();
    while (T--)
    {
        ll n, m, ans = 1;
        scanf("%lld %lld", &n, &m);
        if (n > m) std::swap(n, m);
        for (int i = 1, j; i <= n; i = j + 1)
        {
            j = std::min(n / (n / i), m / (m / i));
            ans = ans * pow(pd[j] * pow(pd[i - 1]) % mod, (n / i) * (m / i) % (mod - 1)) % mod;
        }
        printf("%lld\n", ans);
    }
    return 0;
}