链接： http://acm.hrbust.edu.cn/index.php?
m=ProblemSet&a=showProblem&problem_id=1807
Description
上个星期，小胖子学会了欧拉函数，他得意的说:”在a和b之间有多少个与c互素的数字，这种简单题用欧拉就哦啦。“
但是这次三三又问小胖子。在a和b之间有多少个与c互素的数。
Input
第一行包含一个整数t，代表測试次数（1<=1000）。
接下来每一组測试次数输入a。b，c。满足（1<=a<=b<=10^15,1<=c<=10^9）。
Output
对于每组測试输出结果。占一行。
Sample Input
2
1 10 2
3 15 5
Sample Output
5
10
代码及解析例如以下：（数据范围好大）
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <cstdlib>
using namespace std;
typedef long long LL;
LL a, b, n;
vector <long long> vt;
LL solve(LL x, LL n)
{
vt.clear();
for(LL i=2; i*i<=n; i++) { //对n进行素数分解
if(n%i == 0) {
vt.push_back(i);
while(n%i == 0) n /= i;
}
}
if(n > 1) vt.push_back(n);
LL sum = 0, val, cnt;
for(LL i=1; i<(1<<vt.size()); i++) { //用二进制来1,0来表示第几个素因子是否被用到,如m=3，三个因子是2,3,5。则i=3时二进制是011，表示第2、3个因子被用到
val = 1, cnt = 0;
for(LL j=0; j<vt.size(); j++) {
if(i & (1<<j)) { //推断第几个因子眼下被用到
val *= vt[j];
cnt++;
}
}
if(cnt & 1) sum += x/val; //容斥原理，奇加偶减
else sum -= x/val;
}
return x-sum;
}
int main()
{
int cas;
scanf("%d", &cas);
while(cas--) {
cin >> a >> b >> n;
cout << solve(b, n) - solve(a-1, n) << endl;
}
return 0;
}