题意：给定区间和n，求区间中与n互素的数的个数, 。
思路：利用容斥定理求得先求得区间与n互素的数的个数，设表示区间中与n互素的数的个数, 那么区间中与n互素的数的个数等于。详细分析见求指定区间内与n互素的数的个数 容斥原理
AC代码
#include <cstdio>
#include <cmath>
#include <cctype>
#include <bitset>
#include <algorithm>
#include <cstring>
#include <utility>
#include <string>
#include <iostream>
#include <map>
#include <set>
#include <vector>
#include <queue>
#include <stack>
using namespace std;
#pragma comment(linker, "/STACK:1024000000,1024000000")
#define eps 1e-10
#define inf 0x3f3f3f3f
#define PI pair<int, int>
typedef long long LL;
const int maxn = 1e4 + 5;
LL solve(LL r, int n) {
vector<int>p;
p.clear();
for(int i = 2; i*i <= n; ++i) {
if(n % i == 0) {
p.push_back(i);
while(n % i == 0) n /= i;
}
}
if(n > 1) p.push_back(n);
LL sum = 0;
for(int msk = 1; msk < (1<<(p.size())); ++msk) {
LL mult = 1, bits = 0;
for(int i = 0; i < p.size(); ++i) {
if(msk & (1 << i)) {
bits++;
mult *= p[i];
}
}
LL cur = r / mult;
if(bits & 1) sum += cur;
else sum -= cur;
}
return r - sum;
}
int main() {
LL a, b;
int n;
int T;
scanf("%d", &T);
int kase = 1;
while(T--) {
scanf("%lld%lld%d", &a, &b, &n);
LL x = solve(b, n), y = solve(a-1, n);
//printf("%lld %lld\n", x, y);
printf("Case #%d: %lld\n", kase++, x-y);
}
return 0;
} 如有不当之处欢迎指出！