质数筛法

$\\\\$

1、埃氏筛

for(int j=i;j<=x;j+=i) st[j]=true;//将范围内所有i的倍数的值都删去
因此会重复删除，在$ 10^7 $以上比线性筛慢

2、线性筛

st[prime[j]*i]=true;    //无论如何prime[j]*i都是被最小质因数删去的
if(i%prime[j]==0) break;//要是i能被pj整除，就必须退出循环，继续循环的下一个值一定不是最小质因数

特点：每一个在范围内的非质数都只被它的最小值因子删掉，因此时间是线性的
$\\\\$

约数

$\\\\$

假设$\quad N=(p1^{c1})*(p2^{c2})\*(p3^{c3})\*···\*(pk^{ck}) $

$ p $是质因子，$c$是质因子的次数
$\\\\$
约数个数$\quad res=(c1+1)\*(c2+1)\*(c3+1)\*···\*(ck+1) $
$\\\\$
解释：因为N的每一项都有$ci+1$种可能性并且p都为质因子，不会出现重复的现象，那么k项都有$ci+1$种可能性，k项相乘就是res的表达式
$\\\\$
约数之和$\quad ans=(p1^{0}+p1^{1}+p1^{2}+···+p1^{c1})\*···\*(pk^{0}+pk^{1}+pk^{2}+···+pk^{ck}) $
$\\\\$
解释：当前表达式是化简过的，将当前表达式展开得到的就是全部约数的和，且因全为质数故不存在重复
$\\\\$
$Q$:每一项$(pi^{0}+pi^{1}+pi^{2}+···+pi^{ci})$如何用代码表示
$A$:while(ci--) sum=(sum*pi+1);
$\\\\$

欧拉

欧拉函数

$\\\\$

作用：求1~n-1内与n互质的数的个数

假设$\quad n=(p1^{c1})*(p2^{c2})\*(p3^{c3})\*···\*(pk^{ck}) $

公式：$ \varphi(n)=n*(1-\frac{1}{p1})\*(1-\frac{1}{p2})\*···\*(1-\frac{1}{pk}) $
推导：首先我们要知道欧拉函数是一个积性函数，即：$\varphi(nm)=\varphi(n)\*\varphi(m)\\\\$
$ \varphi(pi^{ci})=pi^{ci}-pi^{ci-1}=pi^{ci}\*(1-\frac{1}{pi}) $
因为p是质数，与p不互质的只有$pi、2pi···pi^{ci-1}\*pi$ 即$pi^{ci-1}$项
综上所述：$$ \varphi(n)=\varphi(p1^{c1})\*\varphi(p2^{c2})\*···\*\varphi(pk^{ck}) \\\\ \varphi(n)=p1^{c1}\*(1-\frac{1}{p1})\*···\*pk^{ck}\*(1-\frac{1}{pk}) \\\\\varphi(n)=n\*(1-\frac{1}{p1})\*(1-\frac{1}{p2})\*···\*(1-\frac{1}{pk}) $$

欧拉定理 $ \quad 若a与b互质则有 a^{\varphi(b)}\equiv1(mod b) $

费马小定理 $ \quad 若p为质数 a^{p-1}\equiv1(mod p)\quad $

$\\\\$
$Q:3^{2019}的最后两位是什么\\\\A:\varphi(100)=40\quad\quad 3^{2019}=3^{40*50+19}=(3^{19}+50)\%100=17+50=67$
$\\\\$

快速幂

$\\\\$
这两种时间复杂度相同都为nlogn

int qmi(int a, int k, int p)  // 求a^k mod p
{
    int res = 1 % p;
    while (k)
    {
        if (k & 1) res = (LL)res * a % p;
        a = (LL)a * a % p;
        k >>= 1;
    }
    return res;
}


long long f(long long a,long long b,long long p)
{
    if(b==1) return a%p;
    if(b%2) return f(a,b-1,p)*a%p;
    else if(b%2==0) return f(a*a%p,b/2,p);
}

$\\\\$

拓展欧几里得算法

$\\\\$
1、求 $ ax+by=gcd(a,b) $ 中的x、y

当$ b = 0 $时 $x=1,y=0$
当$ b != 0 $时 $ax+by=bx’+(a\%b*y’)\\\\ax+by=bx’+(a-a/b\*b)y’\\\\ax+by=ay’+b(x’-a/b\*y’)$
因此 $\quad x=y’\quad y=(x’-a/b\*y’) $
$\\\\$
2、对于一般的方程$ ax+by=c $
设$ d=gcd(a,b) 则当且仅当d|c 有解 $

应用：求逆元 $ ax\equiv1(mod n) n与a互质，x就是逆元 $

$\\\\$

组合数

$\\\\$

1

$当a,b<=2000时\quad C_a^b=C_{a-1}^b\+C_{a-1}^{b-1}$

2

$当a,b<=100000时\quad C_a^b=\frac{!a}{!b\*\!(a-b)} = !a\*(!b)^{-1}\*(!(a-b))^{-1} \\\\$
$Q:如何求(!b)的逆元? \\\\$
$A:\quad (!b)^{-1}=(!(b-1))^{-1}*qmi(b,mod-2,mod) $

3 lucas定理

$当a,b为long long时 mod<100000 求C_a^b\%mod\\\\ C_a^b\%mod\quad=\quad C_{a\%mod}^{b\%mod}\*C_{a/mod}^{b/mod}\quad \%mod$

4

$C_a^b=\frac{!a}{!b\*\!(a-b)}$
用线性筛筛出2-a中全部的质数，遍历每个质数i，算出a中i的次数减去b、a-b中的i的次数就是最后要乘上的i的次数，再用高精度求出
$\\\\$