NOIP 2001 最大公约数和最小公倍数问题(暴力)

淡淡的烟草味﹌ 2022-05-17 09:09 202阅读 0赞

题目描述

输入二个正整数x0，y0（2<=x0<100000，2<=y0<=1000000），求出满足下列条件的P，Q的个数。  
条件：  
1. P，A是正整数；  
2. 要求P，Q以x0为最大公约数，以y0为最小公倍数。  
试求：  
满足条件的所有可能的两个正整数的个数。

输入

每个测试文件只包含一组测试数据，每组两个正整数x0和y0（2<=x0<100000，2<=y0<=1000000）。

输出

对于每组输入数据，输出满足条件的所有可能的两个正整数的个数。  
下面是对样例数据的说明：  
输入3 60  
此时的P Q分别为:  
3 60  
15 12  
12 15  
60 3  
所以，满足条件的所有可能的两个正整数的个数共4种。

分析：水题，直接从x0枚举到y0，然后由最小公倍数和最大公约数得到另一个数字，再判断这两个数是否满足题意，统计次数。

#include<map>
    #include<set>
    #include<cmath>
    #include<queue>
    #include<stack>
    #include<cstdio>
    #include<vector>
    #include<cctype>
    #include<cstring>
    #include<utility>
    #include<cstdlib>
    #include<iomanip>
    #include<iostream>
    #include<algorithm>
    #define Clear(x) memset(x,0,sizeof(x))
    #define fup(i,a,b) for(int i=a;i<b;i++)
    #define rfup(i,a,b) for(int i=a;i<=b;i++)
    #define fdn(i,a,b) for(int i=a;i>b;i--)
    #define rfdn(i,a,b) for(int i=a;i>=b;i--)
    typedef long long ll;
    using namespace std;
    const int maxn = 1e2+7;
    const int inf = 0x3f3f3f3f;
    const double pi=acos(-1.0);
    const double eps = 1e-8;
    int n;
     
    ll read()
    {
        char ch=getchar();ll ret=0,f=1;
        while(ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
        while(ch>='0'&&ch<='9'){ret=ret*10+ch-'0';ch=getchar();}
        return f*ret;
    }
     
    ll gcd(ll a,ll b){return b==0?a:gcd(b,a%b);}
     
    int main()
    {
        ll x0=read();
        ll y0=read();
        int cnt=0;
        for(int i=x0;i<=y0;i+=x0)
        {
            ll a=x0*y0/(1LL*i);
            if(gcd(a,i)==x0&&(a*i)/gcd(a,i)==y0)
                cnt++;
        }
        printf("%d\n",cnt);
        return 0;
    }