D. Count GCD（数论/gcd/素数筛/容斥）

题目
参考

题意

给定n个数ai，1<=ai<=m
构造数组bi，使得gcd(b1,b2,…bi)==ai，1<=bi<=m
问这样的数组bi有多少个，答案对998244353 取模。

思路

首先b1只能取a1
对于i>1，要满足gcd(b1,b2,…bi)==ai，a[i-1]必然可以被a[i]整除，所以，如果存在a[i-1]不能被ai整除，答案为0；
对于i>1，我们要找bi，使得gcd(a[i-1],bi)==ai，bi<=m，化简为gcd(a[i-1]/ai,bi/ai)==1, bi/ai<=m/ai
即求x的个数，使得gcd(a[i-1]/ai,x)==1, x<=m/ai

求一个范围内，与数v互素的个数，我们可以用容斥来解决。
令v=p1^h1+p2^h2+…+pk^hk，其中p1,p2,…,pk为互不相同的素数，hi为它们的幂次。
则x的个数为
+（与1互素的个数）
-（与p1*p2*…*pk/pi互素的个数）
+（与p1*p2*…*pk/(pi*pj)互素的个数）
-…

详见代码

代码

#include 
using namespace std;
#define ll long long
#define pcc pair<char, char>
#define pii pair<int, int>
#define inf 0x3f3f3f3f
const int maxn = 200010;
const int mod = 998244353;

int sub_mod(int x, int y) {
	ll res = 1LL * x % mod - (y % mod);
	res = (res + mod) % mod;
	return res;
}
int add_mod(int x, int y) {
	return (1LL * x + y) % mod;
}
int n, m;
int a[maxn];
vector<int> p;
// 预处理a[0]的所有素数 
void get_prime(int n) {
	p.clear();
	int x = 2;
	while (x * x <= n) {
		if (n % x == 0) {
			p.push_back(x);
			while (n % x == 0) {
				n /= x;
			}
		}
		++x;
	}
	if (n > 1) {
		p.push_back(n);
	}
}

int cal(int x, int limit) {
	vector<int> px;
	// 因为 x能整除 a[0] 我们从a[0]的素数即可找出x的素数 
	for (auto v: p) {
		if (x % v == 0) {
			px.push_back(v);
		}
	}
	int sz = px.size();
	int ans = 0;
	// 枚举所有的素数组合 
	for (int mask = 0; mask < (1 << sz); ++mask) {
		int cur = 1, cnt = 0;
		for (int i = 0; i < sz; ++i) {
			if (mask & (1 << i)) {
				cur *= px[i];
				++cnt;
			}
		}
		if (cnt & 1) { // 素数出现奇数次 减去贡献 
			ans = sub_mod(ans, limit / cur);
//			ans -= limit / cur;
		} else { // 素数出现偶数次 加上贡献 
			ans = add_mod(ans, limit / cur);
//			ans += limit / cur;
		}
	}
	return ans;
}

void solve() {
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; ++i) {
    	scanf("%d", &a[i]);
	}
	bool ok = true;
	for (int i = 1; i < n; ++i) {
		if (a[i-1] % a[i]) {
			ok = false;
			break;
		}
	}
	if (!ok) {
		printf("0\n");
		return;
	}
	get_prime(a[0]);
	ll ans = 1;
	for (int i = 1; i < n; ++i) {
		ans = ans * cal(a[i-1] / a[i], m / a[i]) % mod;
	}
	printf("%lld\n", ans);
}
int main() {
    int t = 1;
    scanf("%d", &t);
    int cas = 1;
    while (t--) {
//		printf("cas %d:\n", cas++);
        solve();
    }

}
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