题目

 

 

分析

莫比乌斯反演。

还不是很熟练qwq

 

代码

//bzoj1101//给出a,b,d,询问有多少对二元组(x,y)满足gcd(x,y)=d.x<=a,y<=b#include 
      
       using namespace std;const int maxn = 50010;int n, p[maxn];int mu(int m) {    int tmp=0, k=m;    for(int i=2;i*i<=k;i++) {        if(!(m%i)) {            tmp++; m/=i;            if(!(m%i)) return 0;        }    }    if(m>1) tmp++;    return (tmp&1)?-1:1;}int main() {    for(int i=1;i<=maxn-10;i++)        p[i] = p[i-1] + mu(i);    scanf("%d",&n);    for(int i=1;i<=n;i++) {        int a, b, d;        scanf("%d%d%d",&a,&b,&d);        a/=d; b/=d;        if(a>b) swap(a,b);        int c=0,ans=0;        for(int j=1;j<=a;j=c+1) {            c=min(a/(a/j), b/(b/j));            ans+=(p[c]-p[j-1])*(a/j)*(b/j);        }        printf("%d\n",ans);    }    return 0;}