数论–欧几里得定理（求最大公约数）

辗转相除法：

 1 #include<iostream>
 2 using namespace std;
 3 int gcdint a,int b)
 4 {
 5     return a%b==0 ? b : gcdb,a%b);
 6 }
 7 int main)
 8 {
 9     int a,b;
10     cin>>a>>b;
11     cout<<gcda,b);
12     return 0;
13 }

1 int gcdint a,int b)
2 {
3      return b==0?a:gcdb,a%b);
4 }

等价于上面的

1 int gcdint x, int y) 
2 {
3     ify == 0) return x;
4     ifx < y) return gcdy,x);
5     else return gcdy, x%y);
6 }

辗转相减法：

 1 #include<iostream>
 2 using namespace std;
 3 int gcdint a,int b)
 4 {
 5     ifa>b)
 6     {
 7         return gcda-b,b);
 8     }
 9     ifa<b)
10     {
11         return gcda,b-a);
12     }
13     //ifa==b)
14     return a;
15 }
16 int main) 
17 {
18     int a,b;
19     cin>>a>>b;
20     cout<<gcda,b);
21     return 0;
22 }

 非递归算法

 1 int gcdint x,int y)  
 2 {  
 3     int tmp;  
 4     whiletmp = x%y)  
 5     {  
 6         x = y;  
 7         y = tp;  
 8     }  
 9     return y;  
10 }