#35384: c++殘風解
a024. 最大公因數(GCD)
| From: [114.27.20.69] |
發表日期
:
2023-05-30 18:38
先說解答放在最後面XD。
剛開始直接暴力解像這樣:
#include<bits/stdc++.h>
using namespace std;
int main(){
int a,b,k;
cin>>a>>b;
if(b>a){
swap(a,b);
}
for(int i=1;i<=b;i++){
if(a%i==0&&b%i==0){
k=i;
}
}
cout<<k<<endl;
return 0;
}
這個在一般電腦測試下都行，但在ZeroJudge上執行時會出現超時(TLE)。
所以就要用法二(輾轉相除法)。
正解:
#include<bits/stdc++.h>
using namespace std;
int main(){
int a,b,k;
cin>>a>>b;
if(b>a){
swap(a,b);
}
while(a%b!=0){
k=a%b;
a=b;
b=k;
}
cout<<b<<endl;
return 0;
}
ZeroJudge Forum