本文共 5044 字，大约阅读时间需要 16 分钟。

 

gcd

1. //欧几里得，又叫做最大公约数
2. int gcd(int a,int b)
3. {
4.     return b==0?a:gcd(b,a%b);
5. }
6. int gcd(int big, int small)
7. {
8.     if (small > big) swap(big, small);
9.     int temp;
10.     while (small != 0){ //  辗转相除法
11.         if (small > big) swap(big, small);
12.         temp = big % small;
13.         big = small;
14.         small = temp;
15.     }
16.     return(big);
17. }

逆元

1. //逆元
2. gcd(a,b)=a*x+b*y;
3. gcd(b,a%b,)
4. ll extgcd(ll a,ll b,ll &x,ll &y)
5. {
6.     if(b==0){
7.         x=1,y=0;
8.         return a;
9.     }
10.     ll d=extgcd(b,a%b,x,y);
11.     ll t=x;
12.     x=y;
13.     y=t-a/b*y;
14.     return d;
15. }
16. ll inv(ll a,ll mod)
17. {
18.     ll x,y;
19.     extgcd(a,mod,x,y);
20.     return (mod+x%mod)%mod;
21. }

快速幂

1. ll fast_pow(ll a,ll b,ll mod)
2. {
3.     ll ans=1;
4.     while(b){
5.         if(b&1)ans=ans*a%mod;
6.         a=a*a%mod;
7.         b>>=1;
8.     }
9.     return ans;
10. }
11. //快速幂

卡塔兰数

1. #define ll long long
2. ll Catelan[N];
3. //用逆元求解
4. ll extgcd(ll a, ll b, ll& x, ll& y)
5. {
6.     ll d = a;
7.     if(b != 0){
8.         d = extgcd(b, a % b, y, x);
9.         y -= (a / b) * x;
10.     }else {
11.         x = 1;
12.         y = 0;
13.     }
14.     return d;
15. }
16. void pre()
17. {
18.     int i;
19.     ll x, y;
20.     Catelan[0] = 1, Catelan[1] = 1;
21.     for(i = 2; i < N-5; i++)
22.     {
23.         Catelan[i] = Catelan[i-1]*(4*i-2) % mod;
24.         extgcd(i+1, mod, x, y);
25.         Catelan[i] = (Catelan[i]*((x+mod)%mod)) % mod;
26.     }
27. }

矩阵快速幂求逆元

1. #include <cstdio>
2. #include <cstring>
3. #include <algorithm>
4. #define MAXN 100
5. #define LL long long
6. #define MOD 10000
7. using namespace std;
8. struct Matrix
9. {
10.     LL a[MAXN][MAXN];
11.     int r, c;//行数 列数
12. };
13. Matrix ori, res;//初始矩阵 和 结果矩阵
14. void init()//初始化矩阵
15. {
16.     memset(res.a, 0, sizeof(res.a));
17.     res.r = 2; res.c = 2;
18.     for(int i = 1; i <= 2; i++)//构造单位矩阵
19.         res.a[i][i] = 1;
20.     ori.r = 2; ori.c = 2;
21.     ori.a[1][1] = ori.a[1][2] = ori.a[2][1] = 1;
22.     ori.a[2][2] = 0;
23. }
24. Matrix multi(Matrix x, Matrix y)
25. {
26.     Matrix z;
27.     memset(z.a, 0, sizeof(z.a));
28.     z.r = x.r, z.c = y.c;//新矩阵行数等于x矩阵的行数 列数等于y矩阵的列数
29.     for(int i = 1; i <= x.r; i++)//x矩阵的行数
30.     {
31.         for(int k = 1; k <= x.c; k++)//矩阵x的列数等于矩阵y的行数 即x.c = y.r
32.         {
33.             if(x.a[i][k] == 0) continue;//优化
34.             for(int j = 1; j<= y.c; j++)//y矩阵的列数
35.                 z.a[i][j] = (z.a[i][j] + (x.a[i][k] * y.a[k][j]) % MOD) % MOD;
36.         }
37.     }
38.     return z;
39. }
40. void Matrix_mod(int n)
41. {
42.     while(n)//N次幂
43.     {
44.         if(n & 1)
45.             res = multi(ori, res);
46.         ori = multi(ori, ori);
47.         n >>= 1;
48.     }
49.     printf("%lld\n", res.a[1][2] % MOD);
50. }
51. int main()
52. {
53.     int N;
54.     while(scanf("%d", &N), N!=-1)
55.     {
56.         init();//初始化单位矩阵
57.         Matrix_mod(N);//矩阵快速幂
58.     }
59.     return 0;
60. }

斯特灵近似

1. ll steling(ll n)
2. {
3.     return ll(log10(sqrt(4*acos(0.0)*n))+n*log10(n/exp(1.0)))+1;
4. }

判定质数

1. for(int i = 2 ; i * i <= n ; ++ｉ)　｛
2.     if( n % i == 0 )
3.     {
4.         flag = 1 ;
5.         breke;
6.     }
7. ｝

欧拉筛法

求  n 以内的所有质数

1. for(int i = 2 ; i <= n ; ++ i ) {
2.     if( ! vis[i] )
3.     {
4.         cnt ++ ;
5.         p[cnt] = i ;
6.     }
7.     for( int j = 1 ; j <= cnt && i * p[j] <= n ; ++ j )
8.     {
9.         vis[p[j] * i ] = 1 ;
10.         if( i % p[j] == 0 ) break;
11.     }
12. }

欧拉函数

方法一

1. scanf("%lld", &n );
2.         if( n == 0 )
3.             return 0;
4.         long long m = n ;
5.         for(int i = 2 ; i * i <= m ; ++ i )//分解为质数乘积
6.         {
7.             if( m % i == 0 )
8.             {
9.                 cnt ++ ;
10.                 p[cnt] = i ;
11.                 while( m % i == 0 )
12.                 {
13.                     m = m / i ;
14.                     w[cnt] ++ ;
15.                 } 
16.             }
17.         }
18.         if( m != 1 )
19.         {
20.             cnt ++ ;
21.             p[cnt] = m ;
22.             w[cnt] = 1 ;
23.         }
24.         long long ans = 1 ;
25.         for(int i = 1 ; i <= cnt ; ++ i )
26.         {
27.             ans = ans * (p[i] - 1 ) ;
28.             for(int j = 1 ; j < w[i] ; j ++ )
29.             {
30.                 ans = ans *p[i] ;
31.             }
32.         }

方法二

1. ph[1] = 1 ;//结合欧式筛法，可以求出 n 以内每一个数的欧拉函数值
2.     scanf("%d", &n );
3.     for(int  i = 2 ; i <= n ; ++ i ) {
4.         if(!vis[i]) {
5.             cnt ++ ;
6.             pr[cnt] = i ;
7.             ph[i] = i - 1 ;
8.         }
9.         for(int j = 1 ; j <= cnt && i * pr[j] <= n ; ++ j ) {
10.             vis[ i * pr[j] ] = 1 ;
11.             if( i % pr[j] == 0 ) {
12.                 ph[ pr[j] * i ] = ph[i] * pr[j] ;
13.                 break;
14.             }
15.             else
16.                 ph [ pr[j] * i] = ph[i] * (pr[j] - 1 );
17.         }
18.     }
     

原文：

分解质因数

（任何一个大于1的自然数，都能分解为若干个质数的幂的乘积，即）

1. void get(int n)
2. {
3.     for(int i = 2;i * i <= n;i++)
4.         if (n % i == 0){
5.             p[++m] = i;
6.             while(n % i == 0){
7.                 w[m]++;
8.                 n /= i;
9.             }
10.         }
11.     if (n != 1){
12.         p[++m] = n;
13.         w[m] = 1;
14.     }
15. }

欧拉函数

求n以内与n互质的自然数的个数。先求出如上所述的“p”与“w”，再用以下公式：

或者

求二元一次不定方程的整数解

二元一次不定方程形如：ax+by=c(a、b、c是已知参数)，当c是gcd（a，b）的倍数时（gcd（a，b）表a和b的最大公因数），才有整数解。可以用某种算法(即扩展欧几里得算法)求出不定方程ax+by=gcd（a，b）的解（此处x、y不等于上述x、y，因为在算法中把c看作了gcd（a，b），所以解出来x、y缩小了c/gcd（a，b））。

最后求整数解的通解，用如下公式：

其中t为任意整数

1. #include <cstdio>
2. #include <cstring>
3. #include <iostream>
4. using namespace std;
5. int d,x,y;
6. void Sgcd(int a,int b,int &d,int &x,int &y){     //d、x、y要放在全局
7.     if (b == 0){
8.         x = 1;
9.         y = 0;
10.         d = a;
11.         return；
12.     }
13.     else{
14.         Sgcd(b,a % b,d,y,x);
15.         y -= a / b * x;
16.     }
17. }
18. int main()
19. {
20.     int a,b,c;
21.     scanf("%d%d%d",&a,&b,&c);
22.     Sgcd(a,b,d,x,y);
23.     int m = c / d;
24.     printf("%d %d\n",x * m,y * m);//特殊解
25.     printf("%d %d\n",x * m + b / d,y * m - a / d);//其中一个通解，t=1；
26.     return 0;
27. }

排列组合

一、基本公式

（特殊的，0！=1）（以下n>=m）

排列：

表示从n个数中取出m个数来排列的方案总数，忽略顺序。例如：m=2时，（1,2）是一种，（2,1）是另一种。

 

组合:

表示从n个数中取出m个数来组合的方案总数，限制顺序。可以理解为从n个数中取出m个数有多少种取法。例如：m=2时，（1，2）和（2,1）是同一种。m=3时，（1,2,3）和（1,3,2）以及（2,1,3）等是同一种。

二、经典例题

1、将n个相同的球放进m个不同的盒子里。球要放完，盒子不能为空，问有多少种放法。

解：题目等价于有n个球，要在两个球之间插板子（两个球之间最多能插一个），将球分为m个部分。n个球，有n-1个空隙可以插；m个部分，只用m-1个板子。

 

所以又可以等价于有n-1个板子，只需要取m-1个板子，问有多少种取法。因为反正都是把球分为m个部分，所以不同的板子得到的效果是一样的，所以可以理解为是同一种取法。这就是组合。答案：

 

2、将n个相同的球放进m个不同的盒子里。球要放完，盒子可以为空，问有多少种放法。

解：假设盒子不可以为空，放在此题种就等价于你已经放了m个球，还有n个球。所以此题等价于有n+m个球，放在m个盒子里，球要放完，盒子不能为空，这就是第一题了。答案：

 

3.将n个不同的球放在m个相同的盒子里。要求每个盒子里球的数量一样，球要放完（数据保证m是n的因子），问有多少种方法。

解：设n/m=x，即每个盒子里要放x个球。放球时，第一步：在n个球中取出x个球放在一个空盒里，第二步又在剩下的n-x个球中取出x个球放在一个空盒里......直至放完。所以第一步的方法总数是：，到第二步的方法总数是：，一共m步，以此类推。但是有这种情况：已经以某一种方案按要求将所有球放进m个盒子里了，现在却只是将A盒里的球放进B盒里，将B盒里原来的球放进A盒里。因为盒子是一样的，所以这是同一种方法。但计算时却以为是另一种方法。而这个等价于：已经以某一种方案按要求将所有球放进m个盒子里了，现在却只是将盒子调换位置，却认为是不同的方法。调换位置的方法有个。所以最后还要减去。答案：

原文：https://blog.csdn.net/weixin_44025325/article/details/87289230 

转载地址：https://blog.csdn.net/weixin_43960414/article/details/88055995 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！