BZOJ4816【SDOI2017】数字表格 <莫比乌斯反演>

Problem

【SDOI2017】数字表格

Description

刚刚学习了数列。用表示数列的第项，那么

用老师的超级计算机生成了一个的表格，第行第列的格子中的数是，其中表示的最大公约数。
的表格中共有个数，她想知道这些数的乘积是多少。答案对取模。

Input

有多组测试数据。
第一个一个数，表示数据组数。
接下来行，每行两个数。

Output

输出行，第行的数是第组数据的结果。

Sample Input

Sample Output

1
2
3

1
6
960

HINT

Source

鸣谢infinityedge上传

标签：莫比乌斯反演

Solution

转换题目求和的角度为枚举，求对答案的贡献。
那么有

将中间单独分开，设，那么，预处理出的前缀积后数论分块即可。

发现对于每个，最多只会对个的值产生贡献，枚举累加贡献的时间复杂度是调和级数。于是枚举，枚举在内的倍数，将乘到中即可处理出所有。而只能取，于是需要预处理出和即在模意义下的逆元。处理出后再处理的前缀积即可。

时间复杂度。

Code

#include <bits/stdc++.h>
#define MAX_N 1000000
#define MOD 1000000007
using namespace std;
typedef long long lnt;
template <class T> inline void read(T &x) {
    x = 0; int c = getchar(), f = 1;
    for (; !isdigit(c); c = getchar()) if (c == 45) f = -1;
    for (; isdigit(c); c = getchar()) (x *= 10) += f*(c-'0');
}
bool NotPri[MAX_N+5]; int cnt, pri[MAX_N+5]; lnt ans, gp;
lnt mu[MAX_N+5], f[MAX_N+5], g[MAX_N+5], inv[MAX_N+5];
lnt Pow(lnt x, lnt k) {
    lnt ret = 1LL;
    for (; k; k >>= 1, (x *= x) %= MOD)
        if (k&1) (ret *= x) %= MOD;
    return ret;
}
void init() {
    mu[1] = f[1] = inv[1] = 1;
    for (int i = 0; i <= MAX_N; i++) g[i] = 1;
    for (int i = 2; i <= MAX_N; i++) {
        if (!NotPri[i]) pri[cnt++] = i, mu[i] = -1;
        for (int j = 0; j < cnt; j++) {
            if (i*pri[j] > MAX_N) break;
            NotPri[i*pri[j]] = true;
            if (i%pri[j]) mu[i*pri[j]] = -mu[i];
            else {mu[i*pri[j]] = 0; break;}
        }
    }
    for (int i = 2; i <= MAX_N; i++)
        f[i] = (f[i-1]+f[i-2])%MOD, inv[i] = Pow(f[i], MOD-2);
    for (int i = 1; i <= MAX_N; i++) if (mu[i])
        for (int j = i; j <= MAX_N; j += i)
            if (mu[i] == 1) (g[j] *= f[j/i]) %= MOD;
            else (g[j] *= inv[j/i]) %= MOD;
    for (int i = 2; i <= MAX_N; i++)
        (g[i] *= g[i-1]) %= MOD;
}
int main() {
    int T; read(T), init();
    while (T--) {
        int n, m; read(n), read(m), ans = 1LL;
        for (int l = 1, r; l <= min(n, m); l = r+1)
            r = min(n/(n/l), m/(m/l)), 
            gp = g[r]*Pow(g[l-1], MOD-2)%MOD, 
            gp = Pow(gp, 1LL*(n/l)*(m/l)%(MOD-1)), 
            (ans *= gp) %= MOD;
        printf("%lld\n", ans);
    }
    return 0;
}