算法—初等数论

Dear 丶 2022-09-08 14:54 125阅读 0赞

详见转载：[文章链接][Link 1]

下面是自己的笔记：

## 整除和整数 ##

1.**素数的一般判断方法**

试除法

inline bool is_prime(int x){ 
        if(x < 2)
            return false;
        for(register int i = 2; i * i <= x; ++ i)
            if(x % i == 0)
                return false;
        return true;
    }

2.**素数的筛法**  
 质数筛法一般分为埃氏筛和线性筛。

1.**Eratosthenes 筛法 （埃拉托色尼筛法）**  
显然如果 x是合数，那么 x 的倍数也一定是合数。利用这个结论，我们可以避免很多次不必要的检测。

我们可以从小到大枚举分析每一个数，然后同时把当前这个数的所有（比自己大的）倍数记为合数，那么运行结束的时候没有被标记的数就是素数了。

int v[N];
    void primes(int n{ 
        memset(v, 0, sizeof v);
        for(int i = 2;i <= n; ++ i){ 
            if(v[i])continue;
            cout << i << endl;
            for(int j = i;j <= n / i; ++ j)
                v[i * j] = 1;
        }
    }

2.**线性筛（欧拉筛）**(这个不怎么会用)  
详见转载，反正我是没看懂。

3.**最大公因数（GCD）**  
*GCD的性质*  
*更相减损数* gcd(n,m)=gcd(n,n−m)  
*辗转相除法*（欧几里得算法） gcd(n,m)=gcd(m,n%m)  
4.**最小公倍数（LCM）**  
*LCM的性质*  
5.**欧拉函数与互质**

## 整数的取余运算 ##

1.**定义**：d | n 表示d能整除n ，则称d是n的约数，n是d的倍数。（**刚开始学的时候经常搞混**）  
2.**带余数除法**：式子 a=bq+r  
3.**模运算** 常用来限制计算结果的范围

公式：

*  (a+b)%c=(a%c+b%c)%c
 *  (a−b)%c=(a%c−b%c+c)%c
 *  (a×b)%c=(a%c)×(b%c)%c
 *  （乘方运算）

计算减法的时候，通常需要加上模数 c，防止出现负数。  
（除法跟上面的不一样）  
4.**快速幂**  
求a的乘方运算

*递归求解*  
给定整数 a，正整数 n ，以及非零整数 p ，求 a^n % p,利用模 p pp 乘法，这个问题可以递归求解，即令 f ( n ) = a n % p f(n) =an%pf(n)=a n %p，那么f ( n − 1 ) = an − 1 % p f(n-1) = a\{n-1\}%pf(n−1)=an−1%p，f ( n ) = a × f ( n − 1 ) % p f(n) = a\\times f(n-1) % pf(n)=a×f(n−1)%p，这样就转化成了递归式。但是递归求解的时间复杂度为 O ( n )，往往当 n很大的时候就很难在规定时间内得到解了。

*非递归求解*

ll qpow(ll a, ll b, ll q)
    { 
        ll res = 1;//因为是用乘法模拟乘方，所以res要是1
        while(b) { 
            if(b & 1)res = (res * a) % q;//这里判段b是奇数还是偶数
            a = (a * a) % q;//视情况将 * 换成Mul(龟速乘)
            b >>= 1;
        }
        return res % q;
    }

5.**龟速幂**  
6.**费马小定理**  
7.**唯一分解原理**

## 欧几里得算法 ##

1.**扩展欧几里得算法**

*裴蜀（Bézout）定理*  
设 a , b 是不全为零的整数 ，存在无穷多组整数对 ( x , y )， 满足不定方程 a x + b y = d ，其中 d = gcd ⁡ ( a , b ) 即： a x + b y = gcd ⁡ ( a , b )。

扩展欧几里得算法运用了裴蜀（Bézout）定理，来求解（x,y）整数对解。

//在gcd的过程上增加了拓展
    inline int exgcd(int a, int b, int &x, int &y)//不明白这里的a,b和&x,&y有什么区别
    { 
        if(b == 0){ 
            x = 1, y = 0, return a;
        }
        int d = exgcd(b, a % b, x, y);
        int z = x;x = y, y = z - y * (a / b);
        return d;
    }

2.**类欧几里得算法**  
**有好几种算法，先不写，不常考**  
更新ing

[Link 1]: https://blog.csdn.net/weixin_45697774/article/details/113765056?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522162999278816780271598145%2522%252C%2522scm%2522%253A%252220140713.130102334.pc%255Fall.%2522%257D&request_id=162999278816780271598145&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2~all~first_rank_v2~rank_v29-1-113765056.pc_search_result_cache&utm_term=%E7%AE%97%E6%B3%95%E7%AB%9E%E8%B5%9B%E5%88%9D%E7%AD%89%E6%95%B0%E8%AE%BA&spm=1018.2226.3001.4187