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;}新聞熱點
疑難解答
