首页 > > 程序设计 > C/C++ >

一、数论算法

2018-06-17 22:24:13来源：未知阅读 ()

（一）求最大公约数

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

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