（一）求最大公約數 思路：輾轉相除法(歐幾里德演算法) 1 int Gcd(int a,int b) 2 { 3 if(a<b) 4 { 5 int tmp=a; 6 a=b; 7 b=tmp; 8 } 9 while(a%b) 10 { 11 int tmp=a%b; 12 a=b; 13 b=tm ...
（一）求最大公約數
思路：輾轉相除法(歐幾里德演算法)
1 int Gcd(int a,int b) 2 { 3 if(a<b) 4 { 5 int tmp=a; 6 a=b; 7 b=tmp; 8 } 9 while(a%b) 10 { 11 int tmp=a%b; 12 a=b; 13 b=tmp; 14 } 15 return b; 16 }gcd(以int為例)
（二）求最小公倍數
思路：對於整數a,b,lcm(a,b)=a*b/gcd(a,b)
1 int Lcm(int a,int b) 2 { 3 int gcdnum=Gcd(a,b); 4 return a*b/gcdnum; 5 }lcm
(三)求能整除n!的m的最大次冪
思路：
先將M質數分解，然後對M的每個素數因數求N！的最高次冪。
例如M = 45 N = 67，其中45 = 3 ^ 2 * 5 ^ 1，即45的素數因數為3 和 5，而67！中3的最高次冪為31，5的最高次冪為15.這樣就可以確定67！中45的最高冪為15，因為67！中每2個3，1個5就包含 一個45，換句話說也就是求67！中包含了多少（3^2*5^1）這樣的組合，也就是求min （ 31 / 2， 15 / 1 ）。
1 #include <iostream> 2 #include <cstring> 3 using namespace std; 4 int getsum(int n,int x) 5 {//計算1~n之間包含一個因數x的個數 6 int ans=0; 7 while(n) 8 { 9 ans+=n/x; n/=x; 10 } 11 return ans; 12 } 13 int main(int argc, char *argv[]) 14 { 15 int n,m,i,j,t,c=1,temp,ans,a; 16 cin>>t; 17 while(t--) 18 { 19 cin>>m>>n; 20 i=2; ans=1000000; 21 while(m>1) 22 { 23 a=0; 24 while(m%i==0) 25 { 26 a++; m/=i; 27 } 28 if(a) 29 { 30 temp=getsum(n,i)/a; 31 if(ans>temp) ans=temp; 32 } 33 i++; 34 } 35 cout<<"Case "<<c++<<":"<<endl; 36 if(ans) cout<<ans<<endl; 37 else cout<<"Impossible to divide"<<endl; 38 } 39 return 0; 40 }View Code
（四）全排列
1、遞歸實現全排列（所有元素視為不同元素）
1 template<class T> 2 void Swap(T & a, T & b) 3 { 4 T temp = a; 5 a = b; 6 b = temp; 7 } 8 template<class T> 9 void permutations(T list[], int k, int m) 10 { 11 if (k == m) 12 { 13 //copy(list,list+m+1,ostream_iterator<T>(cout,"")); 14 for (int i = 0; i <= m; i++) 15 cout << list[i] << ' '; 16 cout << endl; 17 } 18 else 19 { 20 for (int i = k; i <= m; i++) 21 { 22 Swap(list[k], list[i]); 23 permutations(list, k + 1, m); 24 Swap(list[k], list[i]); 25 } 26 } 27 }View Code
2、STL實現全排列（所有元素視為不同元素）
1 void permutation(char* str, int length) 2 { 3 sort(str, str + length); 4 do 5 { 6 for (int i = 0; i<length; i++) 7 cout << str[i]; 8 cout << endl; 9 } while (next_permutation(str, str + length)); 10 }View Code
3、遞歸實現全排列（重覆元素視為相同元素）
1 template<class T> 2 void permutation(T a[], int t, int n) 3 { 4 if (t == n) 5 { 6 for (int i = 0; i<n; i++) 7 { 8 cout << a[i] << " "; 9 } 10 cout << endl; 11 return; 12 } 13 for (int j = t; j<n; j++) 14 { 15 int flag = 1; 16 for (int r = t; r<j; r++) 17 { 18 if (a[r] == a[j]) 19 { 20 flag = 0; 21 break; 22 } 23 } 24 if (flag == 0) 25 { //不符合條件跳入下一迴圈 26 continue; 27 } 28 swap(a[j], a[t]); 29 permutation(a, t + 1, n); 30 swap(a[j], a[t]); 31 } 32 }View Code
（五）組合
1、對無重覆的n個元素，求取m個元素的組合，並輸出這些組合
1 void dfs(int st, int cur) 2 {//求n個不同的數中取m個元素的組合，調用：dfs(n-1,0);ininum為排好序的且無相同元素的數組，num為臨時數組 3 if (cur>=m) 4 return; 5 for (int i = st; i >= 0; --i) 6 { 7 int v = ininum[i]; 8 vis[v] = 1; 9 num[cur] = v; 10 if (cur == m - 1) 11 { 12 for (int j = 0; j < m; j++) 13 { 14 cout << num[j] << ' '; 15 } 16 cout << endl; 17 } 18 dfs(i - 1, cur + 1); 19 } 20 }View Code
2、對含有重覆元素的n個元素（重覆元素視為相同元素），求取m個不同元素的組合，並輸出這些組合
1 #include <stdio.h> 2 #include <stdlib.h> 3 #define MAX_NUM 26 4 int comb[MAX_NUM]; 5 int c1,c2; 6 void combination(int m,int n) { 7 int i,j; 8 9 for (i=m;i>=n;i--) { 10 comb[n]=i; /* 選擇當前的“頭”元素 */ 11 if (n>1) { 12 combination(i-1,n-1); /* 進入下一次更小的組合問題 */ 13 } else { /* 滿了需要的組合數，輸出 */ 14 for (j=comb[0];j>0;j--) printf("%c",'A'+c1-comb[j]); 15 printf("\n"); 16 } 17 } 18 return; 19 } 20 int main(int argc,char **argv) { 21 if (argc<3) { 22 printf("%s 組合下標 組合上標\n",argv[0]); 23 return 1; 24 } 25 c1=atoi(argv[1]); 26 if (c1<1 || MAX_NUM<c1) { 27 printf("1<=組合下標<=%d\n",MAX_NUM); 28 return 2; 29 } 30 c2=atoi(argv[2]); 31 if (c2<1 || c1<c2) { 32 printf("1<=組合上標<=組合下標\n"); 33 return 3; 34 } 35 comb[0]=c2; 36 combination(c1,c2); 37 return 0; 38 }View Code
(六)容斥原理
原理：
（1）|A∪B∪C|=|A|+|B|+|C|-|A∩B|-|A∩C|-|B∩C|+|A∩B∩C|
（2）|A∪B∪C∪D|=|A|+|B|+|C|+|D|-|A∩B|-|A∩C|-|A∩D|-|B∩C|-|B∩D|-|C∩D|+|B∩C∩D|+|A∩C∩D|+|A∩B∩D|+|A∩B∩C|-|A∩B∩C∩D|
（3）
容斥原理可與二進位位運算枚舉方案數相結合。
（七）快速冪
1、快速冪取模
以下以求a的b次方來介紹
把b轉換成二進位數。
該二進位數第i位的權為 2^(i-1)
例如
11的二進位是1011
11 = 2³×1 + 2²×0 + 2¹×1 + 2º×1
因此，我們將a¹¹轉化為算a^(2^0)*a^(2^1)*a^(2^3)
1 long long quickpow(long long m , long long n , long long k){ 2 long long ans = 1; 3 while(n){ 4 if(n&1) //取b二進位的最低位，判斷和1是否相同，相同返回1，否則返回0，可用於判斷奇偶 5 ans = (ans * m) % k; 6 n = n >> 1; //把b的二進位右移一位，即去掉其二進位位的最低位 7 m = (m * m) % k; 8 } 9 return ans; 10 }View Code
2、矩陣快速冪
1 //定義一個矩陣類，例如求（A^n）%mod 2 class Matrix { 3 public: 4 long long m[MAXN][MAXN]; //二維數組存放矩陣 5 Matrix(){} //對數組的初始化 6 void init(long long num[MAXN][MAXN])//重載矩陣的乘法運算 7 { 8 for(int i = 0 ; i < MAXN ; i++) 9 { 10 for(int j = 0 ; j < MAXN ; j++) 11 { 12 m[i][j] = num[i][j]; 13 } 14 } 15 } 16 friend Matrix operator*(Matrix &m1 ,Matrix &m2) //矩陣的快速冪 17 { 18 int i, j, k; 19 Matrix temp; 20 for (i = 0; i < MAXN; i++) 21 { 22 for (j = 0; j < MAXN; j++) 23 { 24 temp.m[i][j] = 0; 25 for(k = 0 ; k < MAXN ; k++) //註意每一步都進行取模 26 temp.m[i][j] += (m1.m[i][k] * m2.m[k][j])%mod 27 temp.m[i][j] %= mod; 28 } 29 } 30 return temp; 31 } 32 friend Matrix quickpow(Matrix &M , long long n)//初始化為單位矩陣 33 { 34 Matrix tempans; 35 //初始化 36 for(int i = 0 ; i < MAXN ; i++) 37 { 38 for(int j = 0 ; j < MAXN ; j++) 39 { 40 if(i == j) 41 tempans.m[i][j] = 1; 42 else 43 tempans.m[i][j] = 0; 44 } 45 } 46 //快速冪（類似整數） 47 while(n) 48 { 49 if(n & 1) www.2cto.com 50 tempans = tempans * M; //已經重載了* 51 n = n >> 1; 52 M = M * M; 53 } 54 return tempans; 55 } 56 }; 57 58 int main() 59 { 60 Matrix A , ans; 61 long long T , n , k , sum; //數據類型為long long 62 long long num[MAXN][MAXN]; //輸入的數據存入數組 63 scanf("%lld" , &T); 64 while(T--) 65 { 66 scanf("%lld%lld\n", &n , &k); 67 memset(num , 0 , sizeof(num)); 68 for(int i = 0 ; i < n ; i++) 69 { 70 for(int j = 0 ; j < n ; j++) 71 scanf("%lld" , &num[i][j]); 72 } 73 A.init(num);//初始化A矩陣 74 ans = quickpow(A , k);//求出矩陣的快速冪 75 } 76 } 77View Code
