数论

求解gcd：辗转相除法：

1
2
3
4
5
int gcd(int a,int b)
{
    if(!b) return a;
    return gcd(b,a%b);
}

【题目大意】给定\(n,p,n<p,p\in prime\)，求\(1\sim n\)中所有整数在模\(p\)意义下的乘法逆元。

\(a\)模\(p\)的乘法逆元定义为\(ax\equiv 1(\text{mod }p)\)的解

逆元的定义：\(aa'=a'a=e\)，\(e\)为单位元，满足\(e\cdot e=e\)。明显此处1为乘法逆元的单位元，故\(a'\)的计算如题所示

由费马小定理\(a^{p-1}\equiv 1(\text{mod }p),p\in prime,a,p互质\)，可化为\(a^{p-2}\equiv a'(\text{mod }p)\)

单独求解某逆元可使用快速幂，时间复杂度为\(O(\log p)\)

若需要求解一连串的值的逆元，可使用递推法。

记\(p=ki+r,1\le r<i<p(r不可能为0)\)，其中\(k是商，r是余数\)。

\(ki+r\equiv 0(\text{mod } p)\to kr^{-1}+i^{-1}\equiv 0(\text{mod }p)\)

\(\displaystyle i^{-1}\equiv -kr^{-1}(\text{mod }p)\to i^{-1}=-\lfloor\frac{p}{i}\rfloor(p\text{ mod }i)^{-1}(\text{mod }p)\)

时间复杂度为\(O(1)\)

实际在保持被模数为正数时，一般使用\(\displaystyle i^{-1}=(p-\lfloor\frac{p}{i}\rfloor)(p\text{ mod }i)^{-1}(\text{mod }p)\)

并注意整数型数据溢出风险。

欧拉函数\(\varphi(n)\)，指\(1\sim n\)与\(n\)互质的元素个数。

（1）若\(n\in prime,\varphi(n)=n-1\)

（2）将分解质因数得到\(\displaystyle n=\prod_{i=1}^{k}a_i^{p_i},a_i\in prime,p_i\in\mathbb{N_+}\)，有\(\varphi(n)=\displaystyle n\prod_{i=1}^{k}(1-\frac{1}{a_i})\)

筛法

欧拉筛，在埃氏筛的基础上做出改进，埃氏筛的缺陷在于：对于某一个合数，可能会被筛多次，其算法时间复杂度为\(O(n\log\log n)\)，而欧拉筛具有线性复杂度，即\(O(n)\)

在埃氏筛基础上，让每个合数只被它的最小质因子筛一次。

参考代码，以LuoguP3383 线性筛素数为例 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include<bits/stdc++.h>
using namespace std;
const int N=1e8+5;
int isprime[N],prime[N],tot,n,q,x;
int main()
{
    cin>>n>>q;
    for(int i=1;i<=n;i++) isprime[i]=1;
    for(int i=2;i<=n;i++)
    {
        if(isprime[i]) prime[++tot]=i;
        for(int j=1;j<=tot&&prime[j]*i<=n;j++)
        {
            isprime[prime[j]*i]=0;
            if(i%prime[j]==0) break;
        }
    }
    for(int i=1;i<=q;i++)
    {
        scanf("%d",&x);
        printf("%d\n",prime[x]);
    }
    return 0;
}

注意：\(i\text{ mod }prime_j=0\)这一句表明每一个合数仅会被它的最小质因数筛去。当出现此情况时，有\(i=k\cdot prime_j\)，设不跳出，下一个将被筛的数为\(i\cdot prime_{j+1},即k\cdot prime_{j}\cdot prime_{j+1}\)，理应被\(prime_j\)筛去，而非\(prime_{j+1}\)