题目 可知 区间 均为 1 - n；
对于 k gcd （a ， b ） = k； 则 gcd （a / k， b / k ） = 1；
则可枚举 x ， 对于 y ； y 《 x 既是 Phi【x】 （欧拉函数值）
y 》 x ，用容斥原理， 统计出 x 的 质因数的倍数的个数 ，再减去这个值即可
#include#include #include #include using namespace std;typedef long long ll;const int maxn = 1e6+131;int Cnt;int Prime[maxn];bool Jug[maxn];void Make(){ Cnt = 0; for(int i = 2; i < maxn; ++i) { if(Jug[i] == false) { Prime[Cnt++] = i; for(int j = i; j < maxn; j += i) Jug[j] = true; } }}int Phi[maxn];void Phi_table() { for(int i = 2; i < maxn; ++i) Phi[i] = 0; Phi[1] = 1; for(int i = 2; i < maxn; ++i) if(!Phi[i]) for(int j = i; j < maxn; j += i) { if(!Phi[j]) Phi[j] = j; Phi[j] = Phi[j] / i * (i - 1); } }int Num[100][2];int nCnt;int Get_Ncnt(int x){ nCnt = 0; for(int i = 0; i < Cnt && Prime[i] * Prime[i] <= x; ++i) { if(x % Prime[i] == 0) { Num[nCnt][0] = Prime[i]; Num[nCnt][1] = 0; while(x % Prime[i] == 0) { Num[nCnt][1]++; x /= Prime[i]; } nCnt++; } } if(x > 1) { Num[nCnt][0] = x; Num[nCnt][1] = 1; nCnt++; } return nCnt;}int calc(int a,int b){ Get_Ncnt(b); int ans = 0; for(int i = 1; i < (1 << nCnt); ++i) { int cnt = 0, tmp = 1; for(int j = 0; j < nCnt; ++j) if(i & (1 << j)) { cnt++; tmp *= Num[j][0]; } if(cnt & 1) ans += a / tmp; else ans -= a / tmp; } return a - ans;}int main(){ Make(); Phi_table(); int t; scanf("%d",&t); for(int kase = 1; kase <= t; ++kase) { printf("Case %d: ",kase); long long ans = 0; int a,b,c,d,k; scanf("%d%d%d%d%d",&a,&b,&c,&d,&k); if(k > b || k > d || k == 0) { printf("%lld\n",ans); continue; } if(b > d) swap(b,d); b /= k, d /= k; for(int i = 1; i <= b; ++i) ans += Phi[i]; for(int i = b+1; i <= d; ++i) ans += calc(b,i); printf("%lld\n",ans); } return 0;}