@數學題 / 博客 RSS 訂閱

Apr 05 2023

十八閒客 - （算法）GCD，LCM

GCD 輾轉相除得最大公約數。（也叫經典的歐幾里得算法） a,b兩個數，小的那個假如a，另一個數就變小為b%a。 然後不斷遞歸下去，就能得到最大公約數gcd。 code： int gcd(int a,int b){ return b==0?a:gcd(b,a%b); } 時間複雜度logn，非常快。 下面解釋下原理： 1.首先a，b哪個先來被模不重要，輾轉一次

數學題 , 程序設計

收藏 評論