51 lines
1.6 KiB
C++
51 lines
1.6 KiB
C++
#include <bits/stdc++.h>
|
||
using namespace std;
|
||
#define int long long
|
||
#define endl "\n"
|
||
|
||
vector<int> p; // 质数数组
|
||
int cal(int n, int m) { // 返回1-m中与n互素的数的个数
|
||
p.clear(); // 多组测试数据,清空
|
||
// 分解质因数
|
||
for (int i = 2; i * i <= n; i++) { // 对n分解质因数
|
||
if (n % i == 0) {
|
||
p.push_back(i);
|
||
while (n % i == 0) n /= i;
|
||
}
|
||
}
|
||
if (n > 1) p.push_back(n); // 最后一个大因子，也加入
|
||
|
||
int s = 0; // 1到m中与n不互素的数的个数
|
||
|
||
// 枚举子集，不能有空集，所以从1开始
|
||
for (int i = 1; i < 1 << p.size(); i++) { // 从1枚举到(2^素因子个数)
|
||
int cnt = 0;
|
||
int t = 1;
|
||
for (int j = 0; j < p.size(); j++) { // 枚举每个素因子
|
||
if (i & (1 << j)) { // 有第i个因子
|
||
cnt++; // 计数
|
||
t *= p[j]; // 乘上这个质因子
|
||
}
|
||
}
|
||
// 容斥原理
|
||
if (cnt & 1) // 选取个数为奇数，加
|
||
s += m / t;
|
||
else // 选取个数为偶数，减
|
||
s -= m / t;
|
||
}
|
||
return m - s; // 返回1-m中与n互素的数的个数
|
||
}
|
||
|
||
signed main() {
|
||
int T, ca = 0;
|
||
cin >> T;
|
||
|
||
while (T--) {
|
||
int m, a, b;
|
||
cin >> a >> b >> m; // 求区间[a,b]中与m互素的数字个数
|
||
// 计算[1,a-1]之间与m互素的个数
|
||
// 计算[1, b]之间与m互素的个数
|
||
int ans = cal(m, b) - cal(m, a - 1);
|
||
printf("Case #%d: %lld\n", ++ca, ans);
|
||
}
|
||
} |