HDU - 4135 Co-prime（容斥+质因数分解）

传送门

---

题目大意

求$[l,r]$中和$n$互质的数的个数

解题思路

根据容斥定理问题可以转化为$[1,x]$中和$n$互质的个数，然后$solve(r)-solve(l-1)$即可。但是互质的数不好求，问题又变成了求出不互质的数的个数，然后拿$n$减去就得到了互质的个数。

$x,y$不互质等价于$gcd(x,y)\ne 1$，考虑最大公约数在质因数分解下的意义，也就是考虑$n$的每一种质数的组合，求出$n$以内有多少个它的倍数。但是这样会重复计算。假设$n=2^x\ast 3^y$，我们已经统计了$n$以内$2$的倍数的个数$\lfloor \frac{n}{2}\rfloor$，然后再求$n$以内$3$的倍数的个数$\lfloor \frac{n}{3}\rfloor$，显然前者和后者有重复的统计部分，这个重复的部分就是$n$以内$2\ast 3$的倍数的个数，因此我们考虑所有的组合状态，若素数种类数为奇数就加上统计的部分，否则减去统计的部分。

代码

不难得知$int$范围内最多有$9$种质因数，即最大且种类最多的数为$2\ast 3\ast 5\ast ...\ast 23$，那么所有的状态数也只有$(1<<9)-1$种，状压枚举即可。

// // Created by Happig on 2020/10/8 // #include <bits/stdc++.h> #include <unordered_map> #include <unordered_set> using namespace std; #define fi first #define se second #define pb push_back #define ins insert #define Vector Point #define ENDL "\n" #define lowbit(x) (x&(-x)) #define mkp(x, y) make_pair(x,y) #define mem(a, x) memset(a,x,sizeof a); typedef long long ll; typedef long double ld; typedef unsigned long long ull; typedef pair<int, int> pii; typedef pair<ll, ll> pll; typedef pair<double, double> pdd; const double eps = 1e-8; const double pi = acos(-1.0); const int inf = 0x3f3f3f3f; const double dinf = 1e300; const ll INF = 1e18; const int Mod = 1e9 + 7; const int maxn = 2e5 + 10; vector<ll> prime; void init(ll n) { prime.clear(); for (ll i = 2; i * i <= n; i++) { if (n % i == 0) { prime.push_back(i); while (n % i == 0) n /= i; } } if (n > 1) prime.push_back(n); } ll solve(ll r) { ll ans = 0; for (ll s = 1; s < (1 << prime.size()); s++) { ll num = 1, cnt = 0; for (int i = 0; i < prime.size(); i++) { if (s & (1 << i)) { cnt++; num *= prime[i]; } } ll res = r / num; if (cnt & 1) ans += res; else ans -= res; } return r - ans; } int main() { //freopen("in.txt","r",stdin); //freopen("out.txt","w",stdout); ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0); int t, kase = 0; ll l, r, n; cin >> t; while (t--) { cin >> l >> r >> n; init(n); cout << "Case #" << ++kase << ": " << solve(r) - solve(l - 1) << ENDL; } return 0; }