TOJ 3

TOJ 3

題目

https://toj.tfcis.org/oj/pro/3/

t 筆測資,每筆測資包含兩個數 a,b,求 a,b 的最大公因數

想法

可以模擬輾轉相除法求解,詳細過程可以參考講義內容。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
//By Koios1143
#include<iostream>
using namespace std;
int gcd(int n,int m){
if(n%m == 0){
return m;
}
return gcd(m, n%m);
}
int main(){
int t,a,b;
cin>>t;
while(t--){
cin>>a>>b;
cout<<gcd(a,b)<<"\n";
}
return 0;
}

複雜度分析

證明我不知道怎麼證QQ ,不過每筆測資時間複雜度為 O(log min(a,b))

Gitalk 載入中…