luogu P1029 最大公约数和最小公倍数问题

https://www.luogu.org/problem/show?pid=1029

输入二个正整数x0,y0(2<=x0<100000,2<=y0<=1000000),求出满足下列条件的P,Q的个数

条件:

1.P,Q是正整数

2.要求P,Q以x0为最大公约数,以y0为最小公倍数.

试求:满足条件的所有可能的两个正整数的个数.

最大公约数是x0，所以设这两个数为x0*k1 , x0*k2 (其中k1,k2互质）。

由题意得：x0 k1 k2 = y0 (想想对吧？）,所以 k1*k2 = y0 / x0 (当然如果y0 / x0 除不尽的话，呵呵，当然没答案啦（输出0）**）

然后只要穷举k1 , k2 的值，因为 k1*k2 = y0 / x0 是轮换式，所以不妨设 k1 < k2 , 然后从1 ~ floor（sqrt(y0 / x0)）穷举

如果k1， k2 互质，那么就找到 2 组解了，所以 sum += 2 。这样就 OK 啦！！！ - - - - - -

#include<bits/stdc++.h>

using namespace std;

int x,y;

int gcd(int a,int b)

{

    return (b==)?a : gcd(b,a%b);

}

int main ()

{

    while (cin >> x >> y){

        int sum = ;

        if(y % x !=) return *printf("0\n");

        int cnt = y/x;

        for(int i=;i*i<cnt;i++)

        {

            if(cnt%i== && gcd(i,cnt/i)==)

                sum+= ;

        }

        cout<< sum <<endl;

    }

}

巴特西

luogu P1029 最大公约数和最小公倍数问题

最新文章

热门文章