4030: a math problem(hard version)
内存限制：128 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：176
解决：24
题目描述
注:easy version和hard version只有数据范围有区别，其他相同
如果两个数的最大公因数是1，那么我们说这两个数是互质的
现在给出两个正整数L和R(L<=R)，再给出一个正整数x，请你求出在L,L+1,L+2, ... ,R-1,R这(R-L+1)个数中，有多少数和x互质
如果两个数的最大公因数是1，那么我们说这两个数是互质的
现在给出两个正整数L和R(L<=R)，再给出一个正整数x，请你求出在L,L+1,L+2, ... ,R-1,R这(R-L+1)个数中，有多少数和x互质
输入
输入只有一行三个用空格隔开的整数L,R,x (1<=L<=R<=1e18,1<=x<=2e9)
输出
输出一个整数表示答案
样例输入 复制
1 10 2
样例输出 复制
5