寒鸽儿のBlog

三题暴力拿Rnk5很丢人的好伐

T1 数论

$n \leqslant 20$ , 枚举所有倍数容斥原理做即可。 复杂度$\mathcal{O(2^n nlogr)}$

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

typedef long long ll;

vector<ll> v;
ll ans = 0, l, r;
int n;

void dfs(int cur, ll lcm, int sign) {
	if(cur == n) {
		ans += (r / lcm  - (l - 1) / lcm) * sign;
		return;
	}
	dfs(cur + 1, lcm, sign);
	ll g = __gcd(lcm, v[cur]);
	if((double)lcm / g * v[cur] <= r)
		dfs(cur + 1, lcm / g * v[cur], -sign);
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n >> l >> r;
	v.resize(n);
	for(int i = 0; i < n; ++i)
		cin >> v[i];
	dfs(0, 1, 1);
	cout << r - l + 1 - ans << '\n'; 
	return 0;
}

T2 术论

正在咕。。。

T3 数论

正在咕。。。