CF585E Present for Vitalik the Philatelist

IOI2020集训队作业

zzz?保持你的决心!

顺带表示期中没炸还好啊

有一个包含 $n$ 个 $\in [2, 10^7]$ 的整数的可重集合。
要求满足条件的一个元素 $x$ 和一个集合 $S$ 的方案数。
条件 $x \notin S$ ， $\gcd\{S\} > 1$ ， $\gcd(x, \gcd\{S\}) = 1$ 。
$n \le 5 \times 10^5$ ，答案对 $10^9+7$ 取模。

自闭了,一看就不是基础计数,就是我不会做的题

$S_n$ 表示最大公约数恰好为n的集合个数, $f_n$ 表示与n互质的数个数

\sum_i {S_if_i}

就是答案

考虑求出S和f,考虑 $f_i$ , $c_i$ 表示i出现次数

f_n=\sum[gcd(i,n)==1]c_i

=\sum_i c_i \sum_{d|i,d|n}\mu(d)

=\sum_{d|n}\mu(d)\sum_{d|i}c_i

g_k=\sum_{k|i}c_i,g_k'=\mu(k)g_k

那么 $g_i$ 就表示i的倍数出现次数,再考虑求 $s_i$ ,令 $s_i'$ 表示最大公因数为i倍数的方案数,要使最大公因数为i的倍数,那么每个选的数必须是i的倍数, $s_i'=2^{g_i}-1$

那么就是这个形式 $b_k=\sum_{i|k}a_i$ , $b_k=\sum_{k|i}a_i$

然后是一个狄利克雷前缀和和一个狄利克雷后缀和,都可以 $O(wlognlogn)$

但还有个问题，已知 $a$ 求 $b$ 能做了，但是那个 $s$ 的计算，是已知 $b$ 求 $a$ 的。

前面是加，那现在就把它逆回去就好了。具体就是把两重循环的反向，然后把加法改成减法就可以辣。当然也可以用高维前缀和的知识解释。

##注意i|d是i是d的因数,d|i才是d是i的因数...##

总时间复杂度 $O(n+w\log\log w)$ 。

这个jj了

code:


#include<iostream>
#include<algorithm>
using namespace std;
#define ll long long
const int MAXN = 5e5 + 7;
const int MAXM = 1e7 + 9;
const int P = 1e9 + 7;
int isp[MAXM], pri[MAXM / 10];
int S[MAXM], _2[MAXN], a[MAXN], tot[MAXM], g[MAXM], cnt, mu[MAXM];
bool vis[MAXM];

inline void upd(int &a) {
	a += (a >> 31)& P;
	//处理负数
}
int n, lim, ans;

void sieve(const int n) {
	mu[1] = 1;
	for(int i = 2; i <= n; ++i ) {
		if(!isp[i]) {
			pri[++cnt] = i;
			mu[i] = -1;
		}
		for(int j = 1; j <= cnt && i * pri[j] <= n; ++j) {
			isp[i * pri[j]] = 1;
			if(i % pri[j] == 0) {
				mu[i * pri[j]] = 0;
				break;
			} else mu[i * pri[j]] = -mu[i];//处理mu
		}
	}
}

int main() {
	for(int i = *_2 = 1; i <= 500000; ++i)
		upd(_2[i] = _2[i - 1] * 2 - P);//fast
	scanf("%d", &n);
	for(int i = 1; i <= n; ++i)scanf("%d", &a[i]), ++tot[a[i]];
	lim = *max_element(a + 1, a + n + 1);//....
	sieve(lim);//fast
	for(int i = 1; i <= cnt; ++i) {
		for(int j = lim / pri[i]; j; --j) {
			tot[j] += tot[j * pri[i]];
		}
	}
	for(int i = 1; i <= lim; ++i)g[i] = tot[i] * mu[i];
	for(int i = 1; i <= cnt; ++i) {
		for(int j = 1; j * pri[i] <= lim; ++j) {
			g[j * pri[i]] += g[j];
		}
	}
	for(int i = 1; i <= lim; ++i)S[i] = _2[tot[i]] - 1;
	for(int i = cnt; i; --i) {
		for(int j = 1; j * pri[i] <= lim; ++j) {
			upd(S[j] -= S[j * pri[i]]);
		}
	}
	for(register int i = lim; i > 1; --i) {
		ans = (ans + 1ll * S[i] * g[i]) % P;
	}
	printf("%d\n", ans);
	return 0;
}

夏晓光(loveJY)的博客

EI5e5差值