[HDU6439]Congruence equation。单独整理的题一般难度都比较大，其实是因为我WA了6发

题解

        先考虑如何处理：

        根据裴蜀定理，我们知道上式有解等价于$gcd(m,C_1,\cdots,C_k)=1$。
        当$A$不全是$-1$时，考虑所有已经存在的数。
        如果已经存在的数的最大公因数为$g$，则$gcd(m,C_1,\cdots,C_k)=1$必然也是$g$的因子。因此，我们在$g>0$的时候，可以较快地统计答案。
        具体来说，当固定一个$m$时，答案应该是：

        对右侧莫比乌斯反演：

        只统计$g$的因子：

        那么总共的答案当然就是：

        于是我们只需要求出最大公因数$g$，然后$O(\sqrt n)$地求出它的所有因子，然后枚举因子得到答案。右侧的求和式需要使用伯努利数求和得到，该操作的预处理复杂度为$O(k^2)$，求和复杂度$O(klogk)$。
        当全部的数都是$-1$或者$g=0$时，我们无法得到一个有效的最大公因数来确定答案域，从而降低复杂度。从上文的推导过程不难发现，此时的答案为：

        利用整除分块配合莫比乌斯函数前缀和可以快速地求出这个和。但是由于$n$很大，我们需要使用杜教筛，这样处理前缀和的复杂度为$O(n^{\frac{2}{3}})$，考虑到伯努利数求和复杂度为$O(klogk)$，所以总复杂度可达$O(n^{\frac{2}{3}}klogk)$。
        综合考察伯努利数，莫比乌斯反演，整除分块以及杜教筛，可以。

代码

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
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
#include <bits/stdc++.h>

using namespace std;
const int mod = 1e9 + 7, N = 5000000;
typedef long long ll;
int C[60][60], S[60], B[60];
int ms[N + 5], vis[N + 5], prim[N + 5], tot;
unordered_map<int, int> mmp;
inline int qpow(int x, int y)
{
    int ans = 1, sta = x;
    while (y) {
        if (y & 1) ans = 1ll * ans * sta % mod;
        sta = 1ll * sta * sta % mod, y >>= 1;
    }
    return ans;
}
inline int inv(int x)
{
    return qpow(x, mod - 2);
}
void init()
{
    ms[1] = 1;
    for (int i = 2; i <= N; i++) {
        if (!vis[i]) ms[i] = -1, prim[++tot] = i;
        for (int j = 1; j <= tot; j++) {
            if (1ll * prim[j] * i > N) break;
            vis[i * prim[j]] = 1;
            if (i % prim[j]) {
                ms[i * prim[j]] = -ms[i];
            } else {
                break;
            }
        }
    }
    for (int i = 2; i <= N; i++) ms[i] = (ms[i] + ms[i - 1]) % mod;
    C[0][0] = C[1][0] = C[1][1] = 1;
    for (int i = 2; i < 60; i++) {
        C[i][0] = C[i][i] = 1;
        for (int j = 1; j < i; j++) C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % mod;
    }
    B[0] = 1;
    for (int i = 1; i < 60; i++) {
        for (int j = 0; j < i; j++) B[i] = (B[i] + 1ll * C[i + 1][j] * B[j] % mod) % mod;
        B[i] = -1ll * B[i] * inv(i + 1) % mod;
    }
}

int getMuSum(int x)
{
    if (x <= N) return ms[x];
    if (mmp.count(x) != 0) return mmp[x];
    int ans = 0, l = 2, r;
    while (l <= x) {
        r = x / (x / l);
        ans = (ans + 1ll * (r - l + 1) * getMuSum(x / l) % mod) % mod;
        l = r + 1;
    }
    return mmp[x] = 1 - ans;
}

inline int getS(int n, int d)
{
    int s = 0;
    for (int i = 0; i <= d; i++) {
        s = (s + 1ll * C[d + 1][i] * B[i] % mod * qpow(n + 1, d + 1 - i) % mod) % mod;
    }
    s = 1ll * s * inv(d + 1) % mod;
    return d == 0 ? s - 1 : s;
}
int gcd(int x, int y)
{
    return y == 0 ? x : gcd(y, x % y);
}
vector<int> P, yz;
inline int getMu(int x)
{
    int mu = 1;
    for (int i = 0; i < P.size(); i++) {
        if (x % P[i] == 0) {
            mu *= -1;
            if (x / P[i] % P[i] == 0) return 0;
        }
    }
    return mu;
}

int main()
{
    init();
    int T, k, n, a, g;
    scanf("%d", &T);
    for (int TT = 1; TT <= T; TT++) {
        scanf("%d%d", &k, &n), a = 0, g = -1;
        P.clear(), yz.clear();
        for (int i = 1, x; i <= k; i++) {
            scanf("%d", &x);
            if (x == -1) {
                ++a;
            } else if (g == -1) {
                g = x;
            } else {
                g = gcd(g, x);
            }
        }
        if (g == -1 || g == 0) {
            int l = 1, r, s, ans = 0;
            while (l <= n) {
                r = n / (n / l), s = getS(n / l, a);
                ans = (ans + 1ll * (getMuSum(r) - getMuSum(l - 1)) * s % mod) % mod;
                l = r + 1;
            }
            printf("Case #%d: %d\n", TT, (ans + mod) % mod);
            continue;
        }
        for (int i = 1; 1ll * i * i <= g; i++) {
            if (g % i == 0) {
                yz.push_back(i);
                if (g / i != i) yz.push_back(g / i);
            }
        }
        for (int i = 2; 1ll * i * i <= g; i++) {
            if (g % i == 0) {
                P.push_back(i);
                while (g % i == 0) g /= i;
            }
        }
        if (g != 1) P.push_back(g);
        int ans = 0;
        for (int i = 0; i < yz.size(); i++) {
            int mu = getMu(yz[i]);
            int S = getS(n / yz[i], a);
            ans = (ans + 1ll * S * mu % mod) % mod;
        }
        printf("Case #%d: %d\n", TT, (ans + mod) % mod);
    }
    return 0;
}