算法笔记——数论基础___gcd时间复杂度

终于学到了数论。。。

1.最大公约数

gcd（a，b）STL 中有__gcd()使用非常的方便。

gcd是一种非常常见的操作，小学时就学会它的求法。

设 a = k * x, b = k * y, k为gcd(a, b)， 那么显然gcd（b, a-b）= k;

这个运算可以压缩为gcd（a， b） = gcd（b， a%b）；

当b == 0 时 gcd（a，b） = a；

而最小公倍数 a*b/gcd(a, b) a与b自有的质因子与其共有的质因子

2.扩展欧几里得

扩展欧几里得可以解决不定方程 a*x  + b*y = c;

我们知道a*x+b*y = gcd(x, y)一定有多组解；

如果c 为 gcd(x, y)的倍数， 则该方程一定有解。

怎么求a*x+b*y = gcd(x, y) 的解呢？我们知道gcd(x, y) = gcd(y, x%y) 

设a*x + b*y = gcd(x, y) a2 * y + b2 * (x - [x/y] * y) = gcd(y, x % y) = gcd(x, y);

a2 * y + b2 * x - b2 * [x/y] * y = gcd(), （a2 - b2 * [x/y]) * y + b2* x = gcd(x, y);

我们可以得出 a = b2, b = a2 - b2 * [x/y];

所以我们可以递归求解 当gcd（x, 0）时 a = 1，b = 0 (a * x - 0 = x)

然后以上面的结论一步步往上推递推步，即可获得原方程的解。

然而我们都知道，对于这样的一个二元方程一定是不只有一组解的，刚才我们求的时特解，而它的通解公式是：

x = x +（ b/gcd) * t ;  证明 十分简单：(x + b/gcd)* a + (y + a/gcd)*b = a*x + b*y + a*b/gcd - b*a/gcd;

y = y - ( a/gcd) * t;

所以求出一个特解后，经过一系列的调整，就可以找到合适的解。

时间复杂度logn

3.线性筛

线性筛的原理很简单， 每一个数只被自己最小的质因子筛到。

for(int i = 2; i <= n; i++){
if(!vis[i]) p[++tot] = i;
for(int j = 1; j <= tot; j++)
  if(i * p[j] > n) break;
  if(i % p[j] == 0) {
     vis[i *p[j] = 1;
     break;
  }
  vis[i * p[j]] = 1;
}

对于一个合数i i = p[] * j,  p为其最小质因子， j为一个合数或质数。显然j , p < i; 所以保证每一个数都会被筛到。

if(i %p[j] == 0) vis[i *p[j]] = 1, break; 这句话是线性筛的关键。我们考虑x为i*p[j+1]; 因为i = k * p[i], 所以这个数一定会在未来被p[i]筛到， 不用考虑。

时间复杂度O(n)

//怎么对于一个数质因数分解

找到一个质因子，把这个数的全部质因子除完。O根号n

3.欧拉函数

欧拉函数phi(x) 表示 小于x与x互质的数的个数， 它是一个积性函数。

如何求欧拉函数：

对于单个数， 求出它的全部质因子（我们不关心质因子的个数）ans = n, ans = ans/i*(i-1) // i为质因子

欧拉函数有两个定理 if x|y  && x*x|y -> phi[y] = phi[x] * x;

if(x | y) && x*x|y -> phi[y] = phi[y/x] * x- 1;

我们可以在线性筛时求出多个数的欧拉函数

4.如何求逆元

对于很大的数的除法运算， 直接取模会导致计算错误（还有乘积也是这样， 但可以使用快速幂，或者欧拉定理的推论来求）

 a/b 同余 a*inv[b](mod p) 可以推出 b * inv[b] 同余 1 (mod p)

解法：

1. exgcd 逆元等价于 b * inv[b] - k * p = 1;

2.费马小定理 当p为质数 inv[b] = b ^ p-2;

3.欧拉定理 inv[b] = b^phi[p - 1]

4.递推 我们对于一个i 设 p = k * i + r;

p * i + r 同乘 i^-1, r^-1

i^-1 = - k * r ^-1   inv[i]=(mod-mod/i)*inv[mod%i]%mod;

5.中国剩余定理

用于求解同余方程组

推荐《算法竞赛进阶指南》的证明， 其实简单。

6、排列组合

众所周知， 组合是从n中取m个数组成一个集合，是无序的。排列是从n中取m个做数列，是有序的。

我们可以在On的时间内求出阶乘的乘法逆元，用于计算组合数：

f[1] = 1;
for(int i = 2; i <= n; i++)
   f[i] = f[i-1] * i;
inv[n] = qpow(f[n], mod - 2) //用各种方法求逆元
for(int i = n - 1; i >= 1; i--)
inv[i] = inv[i + 1] * (i + 1) % mod; 

对于我这个蒟蒻来说， 组合数简直是十分的玄学。

摘自https://blog.csdn.net/zxw0819/article/details/71706543

某区有7条南北向街道，5条东西向街道（如图） 

⑴图中共有多少个矩形？ 
⑵从A点到B点最近的走法有多少种？

分析：⑴在7条竖线中任选2条，5条横线中任选2条，这样4条线 
可组成1个矩形，故可组成矩形C（7,2）·C（5,2）=210个 
⑵每条东西向的街道被分成6段，每条南北向的街道被分成4段，从A到B最短的走法，无论怎样走，一定包括10步，其中6步方向相同，另外4步方向相同，每种走法，即是从10步中选出6步，这6步是走东西方向的，共有C（10,6）=210种走法（同样可以从10段中选出4段走南北方向，每一种选法即是1种走法）。所以共有210种走法。

如果是我的话就大小为2，3～～～的长方形去数了

组合数中非常重要的是多重集合的组合数：

在一个集合中一个元素有多个，选x个（x小于任意一元素的个数）其选择的不同集合的方案与S的大小无关，只与x与其元素的种类有关。公式：C = C(k - 1, k + x - 1);其实我们可以模拟成在x个0中插入k-1个1使其分成k-1个部分，表示每个数选的数量。