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

容斥原理

题意很简单，容易推出，要求：小于 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; }