#include<bits/stdc++.h>
using namespace std;
/*
欧几里得算法（辗转相除法）
    求出两个数字的最大公约数
    gcd(a, b) = gcd(b, a%b);
    通过这样的一个公式，不断的缩小 a 和 b 的值
        直到 b == 0，此时的 a 就是最大公约数
    gcd(14, 36)
    = gcd(36, 14);
    = gcd(14, 8);
    = gcd(8, 6);
    = gcd(6, 2);
    = gcd(2, 0);

求最小公倍数：
    lcm = a * b / gcd(a,b);

*/

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

int main(){
    
    int a, b;
    cin >> a >> b;

    while(b != 0){
        // a,b  -->> b,a%b
        int t = a%b;
        a = b;
        b = t;
    }

    cout << gcd(a,b);
    
    return 0;
}

16 条评论

  • @ 2026-7-23 21:01:37

    小恐龙

    • @ 2026-7-20 11:06:23

      • @ 2026-7-19 21:01:27 
        #include<bits/stdc++.h>
using namespace std;
int gcd(int a,int b){
    if(b==0)return a;
    else return gcd(b,a%b);
}
int main(){ 
    int a,b;
    cin>>a>>b;
    while(b!=0){
        int t=a%b;
        a=b;
        b=t;
    }
    cout<<gcd(a,b);
    return 0;
}

        李懋

        • @ 2026-7-19 21:01:20

          #include<bits/stdc++.h> using namespace std; int gcd(int a, int b){ if(b == 0) return a; else return gcd(b,a%b); } int main(){ int a, b; cin >> a >> b; while(b != 0){ int t = a%b; a = b; b = t; } cout << gcd(a, b); return 0; }

          • @ 2026-7-19 21:00:37 
            #include<bits/stdc++.h>
using namespace std;
int pry(int a,int b){
    if(b == 0){
		return a;
	}else{
		return pry(b,a%b);
	}
}
int main(){
    int a, b;
    cin >> a >> b;
    while(b != 0){
        int t = a%b;
        a = b;
        b = t;
    }
    cout << pry(a,b);
    return 0;
}
            👎 1
            • @ 2026-7-19 21:00:23

              #include<bits/stdc++.h> using namespace std; int gcd(int a,int b){ if(b == 0) return a; else return gcd(b,a%b); }

              int main(){

              int a, b;
cin >> a >> b;
while(b != 0){
	int t = a%b;
	a = b;
	b = t;
}

cout << gcd(a,b);

return 0;

              }

              👎 1
              • @ 2026-7-19 21:00:07

                #include<bits/stdc++.h> using namespace std; int gcd(int a, int b) { if(b ！= 0) { gcd(b, a % b); } else { return a; } } int lcm(int a, int b) { return a * b / gcd(a, b); } int main() { int a, b; cin >> a >> b; cout << gcd(a, b) << ' ' << lcm(a, b); return 0; }

                👎 1
                • @ 2026-7-19 20:59:43 
                  #include<bits/stdc++.h>
using namespace std;
int gcd(int a,int b){
    if(b==0) return a;
    else return gcd(b,a%b);
}
int main(){   
    int a,b;
    cin>>a>>b;
    while(b!=0){
        int t=a%b;
        a=b;
        b=t;
    }
    cout<<gcd(a,b);
}
                  👎 1
                  • @ 2026-7-19 20:58:37 
                    
#include<bits/stdc++.h>
using namespace std;
int gcd(int a,int b){
    if(b==0) 
        return a;
    else 
        return gcd(b,a%b);
}
int main(){
    int a,b;
    cin>>a>>b;
    while(b != 0){
        int t = a%b;
        a=b;
        b=t;
    }
    cout<<gcd(a,b);
}
                    👎 1
                    • @ 2026-7-19 20:58:19

                      #include<bits/stdc++.h> using namespace std; int gcd(int a,int b){ if(b == 0) return a; else return gcd(b,a%b); } int main(){ int a, b; cin >> a >> b; while(b != 0){ int t = a%b; a = b; b = t; } cout << gcd(a,b); return 0; }

                      👎 1
                      • @ 2026-7-19 20:57:30 
                        #include<bits/stdc++.h>
using namespace std;
int gcd(int a, int b) {
    if(b > 0) {
        return gcd(b, a % b);
    } else {
        return a;
    }
}
int lcm(int a, int b) {
    return a * b / gcd(a, b);
}
int main() {
    int a, b;
    cin >> a >> b;
    cout << gcd(a, b) << ' ' << lcm(a, b);
    return 0;
}
                        👎 1
                        • @ 2026-7-19 20:56:43

                          #include <bits/stdc++.h> using namespace std;

                          int f(int a, int b) { while (b != 0) { int temp = a % b; a = b; b = temp; } return a; }

                          int main() { int m, n; cin >> m >> n; cout << f(m, n) << endl; return 0; }

                          👎 1
                          • @ 2026-7-19 20:56:27

                            #include<bits/stdc++.h> using namespace std;

                            gcd(14, 36)
= gcd(36, 14);
= gcd(14, 8);
= gcd(8, 6);
= gcd(6, 2);
= gcd(2, 0);


lcm = a * b / gcd(a,b);

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

                            int main(){

                            int a, b;
cin >> a >> b;

while(b != 0){
    // a,b  -->> b,a%b
    int t = a%b;
    a = b;
    b = t;
}

cout << gcd(a,b);

return 0;

                            }

                            👎 1
                            • @ 2026-7-19 20:56:22 
                              #include<bits/stdc++.h>
using namespace std;
int gcd(int a, int b) {
    if(b > 0) {
        gcd(b, a % b);
    } else {
        return a;
    }
}
int lcm(int a, int b) {
    return a * b / gcd(a, b);
}
int main() {
    int a, b;
    cin >> a >> b;
    cout << gcd(a, b) << ' ' << lcm(a, b);
    return 0;
}
                              👎 1
                            • @ 2026-7-19 20:56:22 
                              #include<iostream>
using namespace std;
int gcd(int a,int b)
{
    if(b==0)return a;

    return gcd(b,a%b); 
}
int main() {
    int a,b;
    cin >> a >> b;
    cout << gcd(a,b);
    return 0;
}
                              • @ 2026-7-19 20:56:03

                                一楼

                              • 1
                              133
                              已通过
                              0
                              题解被赞
                              1. Language
                              2. 主题
                              3. 关于
                              2. 粤ICP备19104337号   可达信奥官网   域
                              5. Powered by Hydro v5.0.4 Community