经验总结

  1. 首页 > 生活 > >

Div. 1 + Div. 2, Rated, Prizes! CodeTON Round 3 A-D( 二 )

生活百科


遍历每个 \(a_i\) 即可 。
时间复杂度 \(O(n(\log a_i + 10\cdot 2^{10}))\)
代码#include <bits/stdc++.h>#define ll long longusing namespace std;const int mod = 998244353;int a[200007];bool vis[100007];int prime[100007];int cnt;void euler_screen(int n) {for (int i = 2;i <= n;i++) {if (!vis[i]) prime[++cnt] = i;for (int j = 1;j <= cnt && i * prime[j] <= n;j++) {vis[i * prime[j]] = 1;if (!(i % prime[j])) break;//如果到了i的最小质因子就不用继续，因为接下去的数x一定能被(i,x)之间的数筛掉}}}///欧拉筛，O(n)，每个合数只会被最小质因子筛掉bool solve() {int n, m;cin >> n >> m;for (int i = 1;i <= n;i++) cin >> a[i];int ans = 1;for (int i = 2;i <= n;i++) {if (a[i - 1] % a[i]) {ans = 0;break;}int d = a[i - 1] / a[i];//不能出现的因子int base = m / a[i];//包含a[i]的数个数vector<int> ft;//对d分解因子种类for (int j = 1;j <= cnt && prime[j] <= d / prime[j];j++) {if (d % prime[j] == 0) ft.push_back(prime[j]);while (d % prime[j] == 0) d /= prime[j];}if (d > 1) ft.push_back(d);int sum = 0;//容斥原理，求[1,base]中没有d中因子的数个数for (int j = 1; j < (1 << ft.size()); j++) {int mul = 1, feat = 0;for (int k = 0; k < ft.size(); k++) {if (j & (1 << k)) {mul *= ft[k];feat++;}}if (feat & 1) sum = (sum + 1LL * base / mul % mod) % mod;else sum = (sum - 1LL * base / mul % mod + mod) % mod;}sum = (base - sum + mod) % mod;ans = 1LL * ans * sum % mod;}cout << ans << '\n';return true;}int main() {std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);int t = 1;cin >> t;euler_screen(100007);while (t--) {if (!solve()) cout << -1 << '\n';}return 0;}【Div. 1 + Div. 2, Rated, Prizes! CodeTON Round 3A-D】

经验总结扩展阅读


上一篇：烤腰果的温度和时间

下一篇：酒精擦发霉衣柜有用么