[SDOI2017]数字表格

Posted on Edited on In Word count in article: 835 Reading time ≈ 3 mins.
RT

[SDOI2017]数字表格

题目大意

求： \[ \prod_{i=1}^n\prod_{j=1}^mf_{\gcd(i,j)} \] 其中： \[ f_i= \begin{cases} 0&i=0\\ 1&i=1\\ f_{i-1}+f_{i-2}&i\ge2 \end{cases} \]

分析

这其实是一个多么裸的题，最多就用了一个欧拉定理。。。

那就直接来吧(规定\(n\le m\)) \[ \begin{aligned} ans&=\prod_{i=1}^n\prod_{j=1}^mf_{\gcd(i,j)}\\ &=\prod_{d=1}^nf_d^{\sum_{i=1}^{\frac nd}\sum_{j=1}^{\frac md}[\gcd(i,j)==1]} \end{aligned} \] 其中，那一坨多么难看的指数可以拉出来特殊关照一下

那么就有 \[ \begin{aligned} \sum_{i=1}^{\frac nd}\sum_{j=1}^{\frac md}[\gcd==1]&=\sum_{i=1}^{\frac nd}\sum_{j=1}^{\frac md}\sum_{k|\gcd(i,j)}\mu(k)\\ &=\sum_{k=1}^{\frac nd}\mu(k)\left\lfloor\frac n{kd}\right\rfloor\left\lfloor\frac m{kd}\right\rfloor\\ \end{aligned} \] 带回原式，可以得到： \[ \begin{aligned} ans&=\prod_{d=1}^n{f_d}^{\sum_{k=1}^{\frac nd}\mu(k)\left\lfloor\frac n{kd}\right\rfloor\left\lfloor\frac m{kd}\right\rfloor}\\ &=\prod_{t=1}^n\prod_{d|t}{f_d}^{\mu(\frac td)\left\lfloor\frac mt\right\rfloor\left\lfloor\frac nt\right\rfloor} \end{aligned} \] 这一步稍微交换一下求值顺序即可得到，然后就是中间多出来的那块求积的东西是可以预处理的，时间复杂度大概是\(\ln n\)级别的，最后的最后就是一个数论分块，因为预处理完后，这个就可以化简为： \[ ans=\prod_{t=1}^nF_t^{\left\lfloor\frac mt\right\rfloor\left\lfloor\frac nt\right\rfloor} \] 这样以来，就十分的显然了，那么到这里，这道题就是真的水完了

唯一值得注意的就是指数那一坨可能特别的大，于是乎可能需要一个欧拉定理之类的东西

但是看到\(n,m\le1e6\)，就知道只需要一个\(ll\)就够了，是否用欧拉定理只是对于常数优化的问题了

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
#include <cstdio>
#include <algorithm>

using namespace std;

typedef long long ll;

const int mod = 1e9 + 7;
const int maxn = 1e6 + 10;

inline int __read()
{
    int x(0);
    char o(getchar());
    while (o < '0' || o > '9') o = getchar();
    for (; o >= '0' && o <= '9'; o = getchar())
        x = (x << 1) + (x << 3) + (o ^ 48);
    return x;
}

inline int Pow(int x, int y)
{
    int ans(1);
    while (y) {
        if (y & 1) ans = 1ll * ans * x % mod;
        x = 1ll * x * x % mod;
        y >>= 1;
    }
    return ans % mod;
}

bool ip[maxn];
int p[maxn], cnt;
int mu[maxn], inv[maxn];
int f[maxn], g[maxn], F[maxn];

inline void Init()
{
    f[1] = g[1] = F[0] = F[1] = 1;
    mu[1] = 1;
    for(int i = 2; i < maxn; ++i) {
        f[i] = (f[i - 1] + f[i - 2]) % mod;
        g[i] = Pow(f[i], mod - 2);
        F[i] = 1;
        if (!ip[i]) p[++cnt] = i, mu[i] = -1;
        for (int j = 1; j <= cnt && i * p[j] < maxn; ++j) {
            ip[i * p[j]] = 1;
            if (i % p[j]) mu[i * p[j]] = -mu[i];
            else break;
        }
    }

    for (int i = 1; i < maxn; ++i) {
        for (int j = i; j < maxn; j += i) {
            if (!mu[j / i]) continue;
            F[j] = 1ll * F[j] * (mu[j / i] == 1 ? f[i] : g[i]) % mod;
        }
    }

    for (int i = 1; i < maxn; ++i) F[i] = 1ll * F[i] * F[i - 1] % mod;
}

int main()
{
    Init();
    int T = __read();
    while (T--) {
        int n = __read(), m = __read();
        if (n > m) swap(n, m);
        int ans(1);
        for (int l = 1, r; l <= n; l = r + 1) {
            r = min(n / (n / l), m / (m / l));
            int temp = 1ll * F[r] * Pow(F[l - 1], mod - 2) % mod;
            ans = 1ll * ans * Pow(temp, 1ll * (n / l) * (m / l) % (mod - 1)) % mod;
        }
        printf ("%d\n", ans);
    }
}

交了以后，发现这两种写法并没有多大的差别，如果想要优化的话，可以考虑离线一下所有的询问，然后可以排个序，这要确实是可以快很多的

至于更多的奇技淫巧可以看看\(loj\)上大佬们的做法