80两TLE求救

tuoran @ 2024-10-20 17:26:00

#include<bits/stdc++.h>

using namespace std;

int main(){
    int a,b;
    cin >> a >> b;
    for(int i = min(a,b);i > 0;i--){
        if(a % i == 0 && b % i == 0){
            cout << i << endl;
            return 0;
        }
    }
}

by Gcc_Gdb_7_8_1 @ 2024-10-20 17:27:25

@tuoran __gcd() 不行吗？

暴力枚举当然超时

by tuoran @ 2024-10-20 17:28:46

蒟蒻没学过__gcd() QWQ

by Gcc_Gdb_7_8_1 @ 2024-10-20 17:30:37

或者手写：

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

by Gcc_Gdb_7_8_1 @ 2024-10-20 17:33:02

@tuoran 《我不如蒟蒻，连通过数都没 Ta 高》

by Gcc_Gdb_7_8_1 @ 2024-10-20 17:33:37

@Gcc_Gdb_7_8_1 的反义词

by tuoran @ 2024-10-20 17:34:26

感谢dalao求互关

by zqw1234 @ 2024-10-20 17:40:42

int gcd(int n, int m){
    if(n == m) return n;
    else if(n > m) return gcd(m, n - m);
    else if(n < m) return gcd(n, m - n);
}

nice递归不超时^_^ （辗转相减法）

或

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

（辗转相除法）

by tuoran @ 2024-10-20 17:45:09

蒟蒻刚刚上网查了一下，这个叫欧几里得算法

by Gcc_Gdb_7_8_1 @ 2024-10-20 17:50:57

@tuoran 不是早就已壶关了吗？

by xuzhengfei666 @ 2024-11-28 21:47:32

@tuoran和你一样