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

2019-9-08 9:30

1,041

未分类

88 字

1 分钟内

链接：P1029

知道两个数的gcd和lcm，很容易知道gcd*lcm就是两数之积

然后我们从二开始枚举每一个因子，检查是不是乘积的因数，如果是，我们就检查这个数和

另一个数的gcd是不是相等就行了

 1 #include<iostream>
 2 
 3 using namespace std;
 4 int gcd(int a,int b){
 5     if(b==0)
 6     return a;
 7     else
 8     return gcd(b,a%b);
 9 }
10 int g;
11 int l;
12 int ans;
13 int main(){
14     cin>>g>>l;
15     int g1=g*l;
16     for(int i=2;i*i<=g1;++i){
17         if(g1%i==0&&gcd(i,g1/i)==g)
18         ans++;
19     }
20     cout<<ans*2;
21     return 0;
22 }