G - GCD and LCM 杭电

Given two positive integers G and L, could you tell me how many solutions of (x, y, z) there are, satisfying that gcd(x, y, z) = G and lcm(x, y, z) = L?
Note, gcd(x, y, z) means the greatest common divisor of x, y and z, while lcm(x, y, z) means the least common multiple of x, y and z.
Note 2, (1, 2, 3) and (1, 3, 2) are two different solutions.

InputFirst line comes an integer T (T <= 12), telling the number of test cases.
The next T lines, each contains two positive 32-bit signed integers, G and L.
It’s guaranteed that each answer will fit in a 32-bit signed integer.OutputFor each test case, print one line with the number of solutions satisfying the conditions above.Sample Input

Sample Output

72

0
昨天想了好久都没想通，，今天早上灵感突然的就来了。
题解：首先我们要理解，最大公约数和最小公倍数的关系，比如说a*b=gcd（a,b）*lcm(a,b) 如果两边同时除以gcd的平方 lcm%gcd==0 所以，如果lcm%gcd!=0的话  应该不会存在关系
第二： 我们让gcd和lcm同时除以gcd可得新的gcd和lcm  gcd=1  lcm=lcm/gcd  他们分别是x/gcd  y/gcd  z/gcd的gcd和lcm 因此我们只要分解lcm/gcd就可以了
第三：lcm=p1^max(a1,a2,a3)*p2^max(b1,b2,b3).... 
　　　   x0=p1^a1....
 　　　　y0=p1^b1...
　　　　z0=p1^c1...
假如说a1 b1  c1 都不为0，那么他们的最大公约数不会是1，因此他们三者中至少有一个为0 ，最多有两个为0（3个为0的情况不会出现，p1一定是其中一个数的只质因子）由于是有顺序的
(0,a1,c1)加入最多的为a1那么C1的取值为0--a1我们先考虑为0和相等的情况 有a1-1中，，变换一下顺序一共有6（a1-1）种,还有(0,0,a1)和（0,a1,a1）我们没考虑共3+3种因此共有6（a1-1）+6种

#include<iostream>

#include<cstdio>

using namespace std;

const int N=1e6+;

bool p[N]={,,};

int prime[N];

int k=;

void pre(){

    k=;

    for(int i=;i<N;i++){

        if(p[i]==){

            prime[k++]=i;

            for(int j=i+i;j<=N;j+=i){

                p[i]=;

            }

        }

    }

}

int main(){

    pre();

    int t;

    cin>>t;

    while(t--){

        int n,m;

        scanf("%d%d",&n,&m);

        if(m%n!=){//最大公约数应该是最下公倍数的系数比如说a*b=gcd*lcm两边同时除以gcd的平方，so lcm%gcd=0

            puts("");

            continue ;

        }

        int x=m/n;

        int sum=;

        for(int i=;i<k&&prime[i]<x;i++){

            if(x%prime[i]==){

                int ans=;

                while(x%prime[i]==){

                    ans++;

                    x=x/prime[i];

                }

                sum*=*ans;

            }

        }

        if(x>) sum*=;

        cout<<sum<<endl;

    }

    return ;

}

巴特西

G - GCD and LCM 杭电

最新文章

热门文章