TOJ 3
題目
https://toj.tfcis.org/oj/pro/3/
有 筆測資,每筆測資包含兩個數 ,求 的最大公因數
想法
可以模擬輾轉相除法求解,詳細過程可以參考講義內容。
Code
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
| #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 ,不過每筆測資時間複雜度為
Gitalk 載入中…