一些基本数学方法

快速幂取模运算

 1 #include <iostream>
 2 using namespace std;
 3 
 4 int main()
 5 {
 6     int a, b, c;
 7     long long ans = 1, base = a;
 8     
 9     a %= c;
10     while (b) {
11         if (b & 1) {
12             ans = (ans * base) % c;
13         }
14         base = (base * base) % c;
15         b >>= 1;
16     }
17     cout << ans;
18 
19     return 0;
20 }

辗转相除法求最大公约数

 1 #include <iostream>
 2 #include <algorithm>
 3 using namespace std;
 4 
 5 void Swap (long long *a, long long *b)
 6 {
 7     long long temp;
 8     temp = *a;
 9     *a = *b;
10     *b = temp;
11 }
12 
13 int main()
14 {
15     long long Max, Min;
16     long long r;
17     long long muy;
18 
19     cin >> Max >> Min;
20     if (Max < Min)
21         Swap(&Max, &Min);
22 
23     muy = Max * Min;
24     while (Min) {
25         r = Max % Min;
26         Max = Min;
27         Min = r;
28     }
29     cout << muy / Max;  //Max为最大公约数
30 
31     return 0;
32 }