Description
FGD正在破解一段密码，他需要回答很多类似的问题：对于给定的整数a,b和d，有多少正整数对x,y，满足x<=a ，y<=b，并且gcd(x,y)=d。作为FGD的同学，FGD希望得到你的帮助。 Input
第一行包含一个正整数n，表示一共有n组询问。（1<=n<= 50000）接下来n行，每行表示一个询问，每行三个 正整数，分别为a,b,d。（1<=d<=a,b<=50000） Output
对于每组询问，输出到输出文件zap.out一个正整数，表示满足条件的整数对数。 Sample Input 2
4 5 2
6 4 3 Sample Output 3
2
//对于第一组询问，满足条件的整数对有(2,2)，（2,4），（4，2）。对于第二组询问，满足条件的整数对有（
6,3），（3,3）。
解题方法： 莫比乌斯反演。 先普及一下莫比乌斯反演， 莫比乌斯反演 贾志鹏线性筛
解题方法来自博主Regina8023的描述。 如果直接枚举d来做会TLE，但是我们发现a’/d的值在d等于好多值得时候都是相同的。
比如a’=100,那么d在[34,50]之间a’/d都是2。
那么我们可以把连续的一段d一起来算（分块）：
设a’/d=x，那么最后一个a’/d=x的d=a’/x，所以这段连续的区间就是[d,a’/(a’/d)]
结合b’/d，取个min就可以了。
代码如下：
#include <bits/stdc++.h>using namespace std;const int maxn = 50005;typedef long long LL;int tot, mu[maxn], PRi[maxn];int sum[maxn];bool mark[maxn];void getMobius(){ mu[1] = 1; tot = 0; memset(mark, 0, sizeof(mark)); for(int i = 2; i <= 50000; i++){ if(!mark[i]) pri[++tot] = i, mu[i] = -1; for(int j = 1; j <= tot && i * pri[j] <= 50000; j++){ mark[i*pri[j]] = 1; if(i % pri[j] == 0){ mu[i*pri[j]] = 0; break; } else mu[i*pri[j]] = -mu[i]; } } sum[0] = 0LL; for(int i = 1; i <= 50000; i++) sum[i] = sum[i-1] + mu[i];}int main(){ getMobius(); int T; scanf("%d", &T); while(T--){ int a, b, D; scanf("%d%d%d", &a, &b, &D); a /= D, b /= D; int x = min(a, b), pos; int ans = 0LL; for(int d = 1; d <= x; d = pos+1){ pos = min(a / (a / d), b / (b / d)); ans += (sum[pos] - sum[d - 1]) * (a / d) * (b / d); } printf("%d/n", ans); } return 0;}新闻热点
疑难解答
