错排问题

又叫错位排列、重排，即使一个排列所有的元素都不在原来的位置上。

1.信封问题

共有 n 张信和 n 个信封，假设所有信都装错了信封，共有多少种情况？

k 号元素的排列有两种方式：

一是放在第 1 个位置，剩下的 n − 2 个元素进行错排，共有 f ( n − 2 ) 种可能；

二是不放在第 1个位置，这时我们将第 1个位置看作第 k 个位置，于是就形成了包括 k 号元素在内的 n − 1个元素的错排，共有 f ( n − 1 ) 种可能。

所以，k号元素共有 f ( n − 1 ) + f ( n − 2 ) 种可能。

又因为第一号元素有 n − 1 种放法，根据乘法原理。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

#include<iostream>
#include<cstdio>

using namespace std;

long long f(long long x)//一定要开long long
{
	if( x == 1 )
		return 0;
	else if( x == 2 )
		return 1;
	else
		return (x-1)*(f(x-1)+f(x-2));
}

int main()
{
	int n;
	cin>>n;
	cout<<f(n);
	return 0;
}

最大公约数

欧几里得算法

求出a和b的最大公约数

1
2
3
4
5
6
7
8

int gcd(int a, int b) {
  while (b != 0) {
    int tmp = a;
    a = b;
    b = tmp % b;
  }
  return a;
}

更相减损术

大整数取模的时间复杂度较高，而加减法时间复杂度较低。针对大整数，我们可以用加减代替乘除求出最大公约数。

$gcd(a,b)\ = \ gcd(a-b,b)$

多个数的最大公约数

答案一定是每个数的约数，那么也一定是每相邻两个数的约数。我们采用归纳法，可以证明，每次取出两个数求出答案后再放回去，不会对所需要的答案造成影响。

最小公倍数

中国剩余定理

解决以下方程组

{

$x\ \equiv a_1(mod\ n_1)$

$x\ \equiv a_2(mod\ n_2)$

$x\ \equiv a_3(mod\ n_3)$

}

1
2
3
4
5
6
7
8
9
10
11

//k 个数，a a数组，r m
LL CRT(int k, LL* a, LL* r) {
  LL n = 1, ans = 0;
  for (int i = 1; i <= k; i++) n = n * r[i];
  for (int i = 1; i <= k; i++) {
    LL m = n / r[i], b, y;
    exgcd(m, r[i], b, y);  // b * m mod r[i] = 1
    ans = (ans + a[i] * m * b % n) % n;
  }
  return (ans % n + n) % n;
}

线性筛

初始时，假设全部都是素数，当找到一个素数时，显然这个素数乘上另外一个数之后都是合数
把这些合数都筛掉，即算法名字的由来。但仔细分析能发现，这种方法会造成重复筛除合数，影响效率。

1
2
3
4
5
6
7
8
9
10
11

int pri[N+9>>1],now;
bool vis[N+9];
void init(){
    for(int i=2;i<=N;i++){
        if(!vis[i])pri[++now]=i;
        for(int j=1;j<=now&&pri[j]*i<=N;j++){
            vis[pri[j]*i]=1;
            if(i%pri[j]==0)break;
        }
    }
}

欧拉函数

求小于等于n和n互质的数的个数

$\alpha(n)$

1
2
3
4
5
6
7
8
9
10
11
12

#include <cmath>

int euler_phi(int n) {
  int ans = n;
  for (int i = 2; i * i <= n; i++)
    if (n % i == 0) {
      ans = ans / i * (i - 1);
      while (n % i == 0) n /= i;
    }
  if (n > 1) ans = ans / n * (n - 1);
  return ans;
}

欧拉定理

$若\ gcd(a,m)\ =\ 1,则a^{\alpha(m) }\ \equiv \ 1\ (mod\ m)$