Song_jiayu @ 2024-12-29 17:20:37
#include<bits/stdc++.h>
using namespace std;
long long gcd(long long x,long long y){
if(max(x,y)%min(x,y)==0){
return min(x,y);
}
for(int i=min(x,y);i>=1;i--){
if(x%i==0 and y%i==0){
return i;
}
}
return 1;
}
long long a,b;
int main(){
cin>>a>>b;
cout<<gcd(a,b);
return 0;
}
by five_rice_water @ 2024-12-29 17:25:13
这种枚举肯定超时啊
by five_rice_water @ 2024-12-29 17:26:51
给出一种方法叫做辗转相除法 证明略
int gcd(int x,int y){
if(y==0) return x;
else return gcd(y,x%y);
}时间复杂度如果我没记错的话好像是