就是计算 区间[1,b/k] [1,d/k] 互质的对数，(3,4) 和(4,3)算一种。每次只加比他大的就行了。
#pragma comment(linker,"/STACK:102400000,102400000") #define _CRT_SECURE_NO_WARNINGS #include<stdio.h> #include<iostream> #include<string> #include<queue> #include<stack> #include<list> #include<stdlib.h> #include<algorithm> #include<vector> #include<map> #include<cstring> #include<set> using namespace std; typedef long long LL; int ans; vector<int> q; int m; void gao(int x, int pre, int flag, int key) { if (x == q.size()) { if (flag) ans += key / pre; else ans -= key / pre; return; } gao(x + 1, pre, flag, key); gao(x + 1, pre*q[x], flag ^ 1, key); } int ask(int n) { int t = n; q.clear(); for (int i = 2; i*i <= t; i++) { if (t%i) continue; while (t%i == 0) t /= i; q.push_back(i); } ans = 0; if (t>1) q.push_back(t); gao(0, 1, 1, m); int cc = ans; ans = 0; gao(0, 1, 1, n-1); // 1 和本身互质 return cc - ans; } int main() { int T, a, b, c, d, k; cin >> T; int Icase = 0; while (T--) { scanf("%d%d%d%d%d", &a, &b, &c, &d, &k); if (k == 0) { printf("Case %d: 0 ", ++Icase); continue; } b /= k; d /= k; if (d < b) swap(b, d); m = d; LL sum = 0; for (int i = 1; i <= b; i++) { sum += ask(i); } printf("Case %d: ", ++Icase); cout << sum << endl;//开始强行加一，会出现等于0的情况。 } return 0; }