405J1R训练（T636402 最大公约数和最小公倍数问题）

pico_fence · 2025-07-21 22:05:12 · 个人记录

正确思路

先定一个gcd函数，再定三个整数函数：n,m,ans，在输入m和n,再来一个for循环：

for(int i=m;i<=n;i++){
    int j=m*n/i;
    if(gcd(i,j)==m && i*j/gcd(i,j)==n){
        ans++;  
    }
}

最后输出ans;

正确代码

#include<bits/stdc++.h>
using namespace std;
int gcd(int x,int y){
    if(y==0){
        return x;
    }
    return gcd(y,x%y);
} 
int n,m,ans; 
int main(){
    cin>>m>>n;
    for(int i=m;i<=n;i++){
        int j=m*n/i;
        if(gcd(i,j)==m && i*j/gcd(i,j)==n){
            ans++;  
        }
    }
    cout<<ans; 
    return 0;
}