（一）求最大公约数

思路：辗转相除法(欧几里德算法)

1 int Gcd(int a,int b) 2 { 3     if(a

（二）求最小公倍数

思路：对于整数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 }

 (三)求能整除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 
      
        2 #include 
       
          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 "<
        
         <<":"<
        
       
      

（四）全排列

1、递归实现全排列（所有元素视为不同元素）

1 template
      
        2 void Swap(T & a, T & b) 3 { 4     T temp = a; 5     a = b; 6     b = temp; 7 } 8 template
       
         9 void permutations(T list[], int k, int m)10 {11     if (k == m)12     {13         //copy(list,list+m+1,ostream_iterator
        
         (cout,""));14         for (int i = 0; i <= m; i++)15             cout << list[i] << ' ';16         cout << endl;17     }18     else19     {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 }
        
       
      

2、STL实现全排列（所有元素视为不同元素）

1 void permutation(char* str, int length) 2 { 3     sort(str, str + length); 4     do 5     { 6         for (int i = 0; i

3、递归实现全排列（重复元素视为相同元素）

1 template
      
        2 void permutation(T a[], int t, int n) 3 { 4     if (t == n) 5     { 6         for (int i = 0; i
      

（五）组合

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 }

2、对含有重复元素的n个元素（重复元素视为相同元素），求取m个不同元素的组合，并输出这些组合

1 #include 
      
        2 #include 
       
         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
       
      

(六)容斥原理

原理：

（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 }

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.com50                 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 } 77