题目大意
求区间内与n互质的数的数量。
解题思路
对于区间显然用[b,1]-[1,a-1]的结果就行了。反过来想，从原来的数中删去与n不互质的数。将n分解质因数，然后利用容斥原理去掉与n有公因数的数即可。
假设分解质因数的结果是2，3，5，观察发现结果就是去掉能被2，3，5整除的数，加上能被2和3，2和5，3和5整除的数，加上能被2和3和5整除的数，当去掉的数是一个奇数项时是减号，偶数项时时加号。同时，每新加入一个质因子，就是在前面的结果上都乘上这个质因子(假设第一个数是1)。
代码
const int maxn = 1e5+10;
const int maxm = 2e2+10;
int p[maxn], u[maxn], q[maxn] = {-1}, __q, k;
vector<int> tmp;
ll solve(ll k, ll x) {
for (int i = 1; (ll)p[i]*p[i]<=x; ++i)
if (x%p[i]==0) {
while(x%p[i]==0) x/=p[i];
tmp.push_back(p[i]);
}
if (x>1) tmp.push_back(x);
ll res = k; __q = 1;
for (auto num : tmp) {
int t = __q;
for (int i = 0; i<t; ++i) q[__q++] = -q[i]*num;
}
for (int i = 1; i<__q; ++i) res -= k/q[i];
tmp.clear();
return res;
}
int main() {
for (int i = 2; i<maxn; ++i) {
if (!u[i]) u[i] = p[++p[0]] = i;
for (int j = 1; i*p[j]<maxn; ++j) {
u[i*p[j]] = p[j];
if (i%p[j]==0) break;
}
}
int t; scanf("%d", &t);
while(t--) {
ll a, b, c; scanf("%lld%lld%lld", &a, &b, &c);
printf("Case #%d: %lld
", ++k, solve(b, c)-solve(a-1, c));
}
return 0;
}