CF585E Present for Vitalik the Philatelist 题解
StayAlone
·
·
题解
只需要普通筛法和简单容斥。
思路
容易想到枚举 S 的 \gcd。
设 \gcd 为 i 的集合数量为 pcnt_i，与 i 不互质的数的数量为 qcnt_i，则答案为 \sum pcnt_i\times (n - qcnt_i)。
考虑如何计算 pcnt 和 qcnt。
$qcnt$ 的计算，考虑子集容斥。对于 $i$，不与之互质的数即**它的所有质因子的倍数**，简单的子集容斥就能避免算重。复杂度看起来不行，实则**不高于枚举因数**，而枚举因数复杂度即枚举倍数复杂度，$\mathcal O(V\ln V)$。
考虑更优美的写法。第二个部分中，对于 $i$，想找到所有贡献给它的 $x$。反过来，对于 $x$，去看它给哪些 $i$ 作贡献。满足条件的 $x$ 的质因子次数均为 $0$ 或 $1$，由奇数偶数判断贡献系数即可。
为了保证复杂度，需要筛法预处理每个数的最小质因子。时间复杂度 $\mathcal O(n+V\ln V)$。
```cpp
// Problem: Present for Vitalik the Philatelist
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/CF585E
// Memory Limit: 250 MB
// Time Limit: 5000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#define rep1(i, l, r) for (int i = l; i <= int(r); ++i)
#define rep2(i, l, r) for (int i = l; i >= int(r); --i)
#define rer(i, l, r, a) rep1(i, l, r) read(a[i])
#define ptc putchar
#define il inline
#define eb emplace_back
#define ef emplace_front
#define mp make_pair
#define fst first
#define snd second
#define sqr(x) ((x) * (x))
#define ls(x) x << 1
#define rs(x) x << 1 | 1
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
// typedef __int128 bll;
// typedef unsigned __int128 ubll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int MAXN = 5e5 + 10, MAXV = 1e7 + 10;
const int LOGN = log2(MAXN) + 1, inf = ~0U >> 2, INF = ~0U >> 1;
const int dx[] = {0, 0, 1, -1}, dy[] = {1, -1, 0, 0};
namespace stupid_lrc {
template <typename T> il bool read(T &x) {
x = 0; bool f = false; char ch;
while (!isdigit(ch = getchar())) {
f ^= !(ch ^ '-');
if (ch == EOF) return false;
}
while (isdigit(ch)) x = (x << 1) + (x << 3) + (ch & 15), ch = getchar();
if (f) x = ~x + 1; return true;
}
il int read() {int x; read(x); return x;}
template <typename T> il bool read(pair <T, T> &x) {return read(x.fst) && read(x.snd);}
template <typename T> il void gmin(T &x, T y) {x = x < y ? x : y;}
template <typename T> il void gmax(T &x, T y) {x = x > y ? x : y;}
template <typename T, typename ...L>
il bool read(T &x, L &...y) {return read(x) && read(y...);}
template <typename T> il T lowbit(const T &x) {return x & -x;}
}
using namespace stupid_lrc;
int n, cnt[MAXV], pw[MAXN]; const int P = 1e7, mod = 1e9 + 7;
ll pcnt[MAXV], ans;
bitset <MAXV> isp; int mip[MAXV], tot, prm[MAXN * 2], qcnt[MAXV];
il void init(int n = P) {
isp.flip(); isp[0] = isp[1] = 0;
rep1(i, 2, n) {
if (isp[i]) mip[i] = i, prm[++tot] = i;
for (int j = 1; j <= tot && prm[j] * i <= n; ++j) {
int now = prm[j] * i;
isp[now] = 0; mip[now] = prm[j];
if (i % prm[j] == 0) break;
}
}
}
il int check(int x) {
int lst = -1, c = 0;
while (x > 1) {
if (mip[x] == lst) return 0;
lst = mip[x]; x /= lst; ++c;
} return c & 1 ? 1 : -1;
}
int main() {
read(n); pw[0] = 1; init();
rep1(i, 1, n) ++cnt[read()], pw[i] = pw[i - 1] * 2 % mod;
rep2(i, P, 2) {
int q = 0; ll &pc = pcnt[i];
for (int j = i; j <= P; j += i) q += cnt[j], pc -= pcnt[j];
pc += pw[q] - 1; pc = (pc % mod + mod) % mod;
if (q *= check(i)) for (int j = i; j <= P; j += i) qcnt[j] += q;
}
rep1(i, 2, P) (ans += pcnt[i] * (n - qcnt[i])) %= mod;
printf("%lld", ans);
return 0;
}
```