当前位置:   article > 正文

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

__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.线性筛

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

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

对于一个合数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的时间内求出阶乘的乘法逆元,用于计算组合数:

  1. f[1] = 1;
  2. for(int i = 2; i <= n; i++)
  3. f[i] = f[i-1] * i;
  4. inv[n] = qpow(f[n], mod - 2) //用各种方法求逆元
  5. for(int i = n - 1; i >= 1; i--)
  6. 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个部分,表示每个数选的数量。

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/Cpp五条/article/detail/75454
推荐阅读
相关标签
  

闽ICP备14008679号