容斥分析_容斥原理的三个公式

(56) 2024-07-29 08:01:01

容斥原理

题意很简单,容易推出,要求:小于 m 的数中,能够被 每个青蛙步距与m的gcd 整除的数的和,

按最基础的学习的容斥原理的话, 难以解决;

所以有了以下代码的解法:

首先找到 m 的所有因子,因为只有这些因子才是 可能会出现重复的点,也是需要我们进行容斥的地方

初始 num 数组为零,用 vis 数组保存能被 某个青蛙的gcd 整除的因数,然后找 num 和 vis 是不是相等,

如果不相等,那么这个因子就是作为一个对 答案进行贡献的 基础元(意思就是,这个数的所有倍数会对答案做出贡献),同时对后面他的倍数进行处理,,

这个 贡献值 也就是(vis - num),表示重复了多加过的次数,或者减多了的次数

建议手动推样例,,会很容易理解

#include<cstdio> #include<cstring> #include<cmath> #include<iostream> #include<algorithm> #include<queue> using namespace std; typedef long long ll; const int maxn =  + 7; int n, m, cnt; int g[maxn], num[maxn], vis[maxn]; int gcd(int a, int b) { return b == 0 ? a : gcd(b, a%b); } void init() { memset(vis, 0, sizeof vis); memset(num, 0, sizeof num); scanf("%d %d", &n, &m); cnt = 0; for(int i = 1; i*i <= m; ++i) { if(m % i == 0) { g[cnt++] = i; if(i*i != m) g[cnt++] = m/i; } } sort(g, g+cnt); for(int i = 0; i < n; ++i) { int x; scanf("%d", &x); int t = gcd(x, m); for(int j = 0; j < cnt; ++j) { if(g[j] % t == 0) { vis[j] = 1; } } } vis[cnt-1] = 0; } void solve() { ll ans = 0; for(int i = 0; i < cnt-1; ++i) { if(vis[i] != num[i]) { int t = (m-1)/g[i]; ans += (ll)t*(t+1)/2 * g[i] * (vis[i]-num[i]); t = vis[i] - num[i]; //cout << g[i] << " = " << t << endl; for(int j = i; j < cnt; ++j) { if(g[j] % g[i] == 0) num[j] += t; } } } cout << ans << endl; } int main() { int T; scanf("%d", &T); for(int tt = 1; tt <= T; ++tt) { init(); printf("Case #%d: ", tt); solve(); } return 0; } 

THE END

发表回复