题目链接:传送门
多组数据问区间内与
互质的数的个数
区间问题显然要转化成两个区间相减的问题
也就是的答案减去
的答案
这里反过来求不互质的数的个数
筛法可以提示我们
分解质因数,通过质因子来筛数
所以我们存下这个的质因子
用二进制的方法枚举每种情况
但是这样筛可能会有重复
比如会被
和
各筛一遍
这就用到了容斥原理奇数加偶数减
不互质的数的个数直接质因子相乘做除法就好了
然后
就没了
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <complex>
#include <algorithm>
#include <climits>
#include <queue>
#include <map>
#include <set>
#include <vector>
#include <iomanip>
#define
#define
using namespace std;
typedef long long ll;
int pri[A], n, T;
ll a, b;
ll sol(ll n, int cnt, ll ans = 0) {
for (int i = 1; i < (1 << cnt); i++) { //二进制枚举所有情况
int tmp = 1, js = 0;
for (int j = 0; j < cnt; j++) {
if ((i >> j) % 2 == 0) continue;
js++; tmp *= pri[j];
}
if (js & 1) ans += n / tmp;
else ans -= n / tmp;
}
return n - ans;
}
int main(int argc, char const *argv[]) {
cin >> T;
for (int k = 1; k <= T; k++) {
cin >> a >> b >> n; int cnt = 0;
for (int i = 2; i * i <= n; i++) //筛质因子
if (n % i == 0) {
while (n % i == 0) n /= i;
pri[cnt++] = i;
}
if (n != 1) pri[cnt++] = n;
cout << "Case #" << k << ": " << sol(b, cnt) - sol(a - 1, cnt) << endl;
}
}