70F

P1029 [NOIP2001 普及组] 最大公约数和最小公倍数问题

Linkaifan1227 @ 2024-10-24 20:16:30

#include<bits/stdc++.h>
using namespace std;
long long m,n,ans;
int gcd(long long wbssb,long long wssb)
{
    int returnx;
    int nn=max(wbssb,wssb);
    for(int i=1;i<=nn;i++)
    {
        if(wbssb%i==0&&wssb%i==0)
        {
            returnx=i;
        }
    }
    return returnx;
}
int main()
{
    cin>>m>>n;
    if(m==n) ans=1;
    long long cnt=n*m; 
    for(long long i=1;i*i<=cnt;i++)
    {
        if(n%i==0&&gcd(i,cnt/i)==m) ans+=2;
    }
    cout<<ans;
    return 0;
}

by Linkaifan1227 @ 2024-10-24 20:17:55

看了大佬解析,但70十分┭┮﹏┭┮


by liyunhe @ 2024-10-24 20:28:45

@Linkaifan1227 可以把gcd的里面改成辗转相除法:

long long gcd(long long a,long long b){
    if (b == 0) {
        return a;
    }
    return gcd(b, a % b);
}

或者直接用__gcd()


|