原题链接
题目描述：对于给出的n个询问，每次求有多少个数对(x,y)，满足a≤x≤b，c≤y≤d，且gcd(x,y) = k，gcd(x,y)函数为x和y的最大公约数。
输入格式：第一行一个整数n，接下来n行每行五个整数，分别表示a、b、c、d、k
输出格式：共n行，每行一个整数表示满足要求的数对(x,y)的个数
输入样例： 2 2 5 1 5 1 1 5 1 5 2
输出格式： 14 3
解析：似乎就是[POI2007]Zap的翻版，最后在计算时用类似二维前缀和的思想计算答案即可。 具体的解析可以看我关于[POI2007]Zap的博客，这里就不在赘述。 POI2007
代码如下：
#include<cstdio> #include<algorithm> #define ll long long using namespace std; const int maxn = 5e4 + 5; int n, mu[maxn], primi[maxn], tot, mark[maxn], k, prim[maxn]; ll sum[maxn]; int read(void) { char c; while (c = getchar(), c < '0' || c >'9'); int x = c - '0'; while (c = getchar(), c >= '0' && c <= '9') x = x * 10 + c - '0'; return x; } void get_mu(void) { mu[1] = 1; mark[1] = 1; int lim = maxn - 5; for (int i = 2; i <= lim; ++ i) { if (!mark[i]) mu[i] = -1, prim[++ tot] = i; for (int j = 1; j <= tot && prim[j] * i <= lim; ++ j) { mark[prim[j] * i] = 1; if (i % prim[j] == 0) break; else mu[prim[j] * i] = -mu[i]; } } for (int i = 1; i <= lim; ++ i) sum[i] = sum[i - 1] + mu[i]; } ll calc(int a, int b) { //计算答案的函数 a /= k; b /= k; int lim = min(a, b); ll ans = 0; for (int l = 1, r; l <= lim; l = r + 1) { r = min(a / (a / l), b / (b / l)); ans += (sum[r] - sum[l - 1]) * (a / l) *(b / l); } return ans; } int main() { get_mu(); n = read(); while (n --) { int a = read(), b = read(), c = read(), d = read(); k = read(); printf("%lld\n", calc(b, d) - calc(a - 1, d) - calc(b, c - 1) + calc(a - 1, c - 1)); //计算答案 } return 0; }转载于:https://www.cnblogs.com/Gaxc/p/10088703.html
相关资源：JAVA上百实例源码以及开源项目