容斥原理

给定a1, a2, a3 , … ,am, 求1到n的整数中至少能整除a中一个元素的数有几个？

---

#include<stdio.h> #define MAX_M 8 typedef long long ll; int a[MAX_M]; int n, m; int gcd(int a, int b) { if (b) while ((a %= b) && (b %= a)); return a + b; } int solve() { ll res = 0; //以二进制的形式讨论 for (int i = 1; i < (1 << m); i++) { int num = 0; for (int j = i; j != 0; j >>= 1)num += j & 1; ll lcm = 1; for (int j = 0; j < m; j++) { if (i >> j & 1) { lcm = lcm / gcd(lcm, a[j])*a[j]; if (lcm > n)break; } } if (num % 2 == 0) res -= n / lcm; else res += n / lcm; } printf_s("%d\n", res); return res; } int main() { scanf_s("%d%d", &n,&m); for (int i = 0; i < m; i++) { scanf_s("%d",&a[i]); } solve(); return 0; }