http://acm.hdu.edu.cn/showproblem.php?pid=1695
要求[L1, R1]和[L2, R2]中GCD是K的个数。那么只需要求[L1, R1 / K] 和 [L2, R2 / K]中GCD是1的对数。
由于(1， 2)和（2， 1）是同一对。
那么我们枚举大区间，限制数字一定是小于等于枚举的那个数字就行。
比如[1, 3]和[1, 5]
我们枚举大区间，[1, 5]，在[1, 3]中找互质的时候，由于又需要要小于枚举数字，那么直接上phi
对于其他的，比如4这样，在[1, 3]中找有多少个数字和它互质。
这需要容斥。先求不互质的个数，因为有个明显的道理，12 = 2 * 2 * 3，那么2的倍数可以排除，3的倍数可以排除，但是排除多了一部分。
区间中与i不互质的个数 = （区间中i的每个质因数的倍数个数）-（区间中i的每两个质因数乘积的倍数）+（区间中i的每3个质因数的成绩的倍数个数）-（区间中i的每4个质因数的乘积）
这个容斥好想但是不好写。我的dfs写的很烂。
#include <cstdio> #include <cstdlib> #include <cstring> #include <cmath> #include <algorithm> #include <assert.h> #define IOS ios::sync_with_stdio(false) using namespace std; #define inf (0x3f3f3f3f) typedef long long int LL; #include <iostream> #include <sstream> #include <vector> #include <set> #include <map> #include <queue> #include <string> const int maxn = 100000 + 20; int prime[maxn];//这个记得用int，他保存的是质数，可以不用开maxn那么大 bool check[maxn]; int total; bool is_prime[maxn]; int his[maxn][50 + 20]; int Size[maxn]; void initprime() { for (int i = 2; i <= maxn - 20; i++) { if (!check[i]) { //是质数了 prime[++total] = i; //只能这样记录，因为后面要用 is_prime[i] = true; } for (int j = 1; j <= total; j++) { //质数或者合数都进行的 if (i * prime[j] > maxn - 20) break; check[i * prime[j]] = 1; if (i % prime[j] == 0) break; //关键，使得它只被最小的质数筛去。例如i等于6的时候。 //当时的质数只有2,3,5。6和2结合筛去了12，就break了 //18留下等9的时候，9*2=18筛去 } } // Size[1] = 1; // his[1][1] = 1; for (int i = 1; i <= maxn - 20; ++i) { if (is_prime[i]) { Size[i] = 1; his[i][1] = i; continue; } int t = i; for (int j = 1; j <= total; ++j) { if (prime[j] > t) break; if (t % prime[j] == 0) { his[i][++Size[i]] = prime[j]; t /= prime[j]; while (t % prime[j] == 0) { t /= prime[j]; } } } } return ; } int phi[maxn]; void init_phi() { phi[1] = 1; for (int i = 2; i <= maxn - 20; i++) { if (!phi[i]) { for (int j = i; j <= maxn - 20; j += i) { if (!phi[j]) phi[j] = j; phi[j] = phi[j] / i * (i - 1); } } } return ; } LL calc(int up, int cur, int number, int tobuild, int flag) { LL ans = 0; for (int i = cur; i <= Size[number]; ++i) { if (flag == 0) { ans += up / (his[number][i] * tobuild) + calc(up, i + 1, number, tobuild * his[number][i], !flag); } else ans += -up / (his[number][i] * tobuild) + calc(up, i + 1, number, tobuild * his[number][i], !flag); } return ans; } int f; void work() { int L1, R1, L2, R2, k; scanf("%d%d%d%d%d", &L1, &R1, &L2, &R2, &k); if (k == 0) { printf("Case %d: 0 ", ++f); return; } R1 /= k; R2 /= k; if (R1 < R2) swap(R1, R2); LL ans = 0; for (int i = 1; i <= R2; ++i) { ans += phi[i]; } for (int i = R2 + 1; i <= R1; ++i) { ans += R2 - calc(R2, 1, i, 1, 0); } printf("Case %d: %I64d ", ++f, ans); } int main() { #ifdef local freopen("data.txt", "r", stdin); // freopen("data.txt", "w", stdout); #endif initprime(); init_phi(); // cout << 24 - calc(24, 1, 12, 1, 0) << endl; // cout << 12 - calc(12, 1, 12, 1, 0) << endl; // for (int i = 1; i <= Size[10]; ++i) { // printf("%d ", his[10][i]); // } int t; scanf("%d", &t); while (t--) { work(); } return 0; }