设 (\displaystyle f(x) = # S’, s.t. S’ \subseteq S, S’ \neq \varnothing, \gcd(S’) = x)，(g(x) = # t, s.t. \gcd(t, x) = 1)，则答案为 (\sum f_i \times g_i)。
- (f)：这个的求解是老套路了，设(\displaystyle F(x) = # S’, s.t. S’ \subseteq S, S’ \neq \varnothing, x \mid S’)，则有(\displaystyle F(x) = 2^{\sum_{x \mid t} \textit{cnt}t}-1)，(cnt) 是桶，(\displaystyle f(x) = \sum{x \mid d} \mu(\frac{d}{x}) \times F(d))，可以调和级数也可以逆 dirichlet 前后缀和（不可以）。
- (g)：写出(\displaystyle g_T = \sum_i [(T, i) = 1] \textit{cnt}i = \sum{d \mid T} \mu(d) \sum_{d \mid i} cnt_i = \sum_{d \mid T} h_d)，其中(h_d = \mu(d) \times w_d)，其中(\displaystyle w_T = \sum_{T \mid i} \textit{cnt}_i)。都是 dirichlet 前后缀和的形式。
using modint = modint1000000007;
bitset tag;
int n, up, tot, prm[10000100], mu[10000100], w[10000100];
modint f[10000100], F[10000100], pw[10000100];
void sieve(int maxn) {
mu[1] = 1;
for (int i=2; i> n;
for (int i=1,x; i> x, w[x]++;
cmax(up, x);
}
sieve(up);
pw[0] = 1;
for (int i=1; i=1; --j) {
w[j] += w[j*prm[i]];
}
}
for (int i=1; i
Original: https://www.cnblogs.com/orchid-any/p/16557474.html
Author: BoringHacker
Title: 「codeforces-585E」Present for Vitalik the Philatelist
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/604064/
转载文章受原作者版权保护。转载请注明原作者出处！