学习笔记--数论知识集合

前言

数论在OI中还是比较重要的,这些笔记是在课上匆忙记下的,可能不太美观。

一些约定:在这里整数间除法是向下取整;$(a,b)$代表$gcd(a,b)$

Problems:

小凯的疑惑
$sol$:构造
$ax+by = k(a,b >= 0)$ 使其无解
设一组解$x1 \in [0,b-1] ,y1>=0$
若$k>ab-a-b$
则$y1>(k-ax1)/b = (ab-a-b-a(b-1))/b $ $= -1$
即$y1>=0$
故$k=ab-a-b$是符合条件的最大值

上帝与集合的正确用法—扩展欧拉定理
https://www.lydsy.com/JudgeOnline/problem.php?id=3884

屠龙勇士—扩展中国剩余定理

用$f(i)​$表示有序三元组(a,b,c)个数,使得$a$\
$b$*$c=i$,求出$f(1)$~$f(n)$
$sol: i=\prod {p_i}^{c_i} $ $ f(i)=\prod C^{ci+2}_2$ 使用扩展欧拉筛

数论之神

Algorithms:

  • 线性推逆元:
    $inv[fac[i]] = inv[fac[i+1]]*(i+1)$

    设$p=i*k+r$

    $i*k+r \equiv 0 \mod p$

    $i*k \equiv -r \mod p$

    $r^{-1}*k \equiv -i^{-1} \mod p$

    $i^{-1} \equiv -p/i * inv[p \% i]$ $\mod p$

  • 中国剩余定理
    ExCRT(增量法):若m不互质
    $x \equiv a \mod b -> x=kb+a $
    $x \equiv c \mod d -> kb+a \equiv c \mod d -> kb+pd = c-a$
    条件$(c-a)|gcd(b,d)$
    求解后回代即可

  • 埃式筛

  • 欧拉筛-扩展 (未懂)

  • Miller-Rabin(未懂)

    费马小定理&&二次剩余

  • Pollard-Rho(未懂)

    生日攻击

  • 类欧几里得算法(未懂)
    https://www.cnblogs.com/LLppdd/p/8428349.html

  • BSGS&&ExBSGS

Other Things:

  1. $\sum_{i=1}^N {1/i} = O(log N)$

    • Prove:
      下界 1/2 * log N
      $\sum_{i=1}^N {1/i} >= 1+1/2+1/4+1/4+1/8+1/8+1/8+1/8+…$
      上界 log N
      $ \sum_{i=1}^N {1/i}<=1+1/2+1/2+1/4+1/4+1/4+1/4+…$
  2. $\sum{1/p} = O(log log N)$

  3. 裴蜀定理: $(a,b)|d $ is equal to $ua+vb=d(u,v \in Z)$

  4. $扩展欧几里得Exgcd:$

    $a \mod b = a-a/b*b$

    $ua+vb = gcd(a,b)$

    $u’b+v’(a mod b) = gcd(a,b)$

    $u’b+v’(a-a/b*b) = gcd(a,b)$

    $v’a+(u’-a/b *$ $v’) * b = gcd(a,b)$

    通解:$x_0=x+t * b/(a,b) ​$ $y_0=y-t * a/(a,b)​$

  5. 一个小性质

    $(k,m)=d$ $且$ $ka \equiv kb \mod m 则 a \equiv b \mod m/d$
    $Prove: ka \equiv kb \mod m -> m|(ka-kb) -> m|k(a-b) -> (m/d)|(a-b)$

  6. 简化剩余系

    • 所有$0<n<=m,(n,m)=1​$的n构成了模m的简化剩余系,简称缩系
      记这样n的个数为$ \phi(m)$

    • 如果$(m,m’)=1$,$a$取遍模$m$缩系,$a’$取遍m’缩系
      那么$am’+a’m$取遍$mm’$缩系

      • $Prove: 已知(a,m)=1,(a’,m’)=1 , (m,m’)=1$
        $(am’,m)=1,(a’m,m’)=1$
        $(am’+a’m,m)=1,(a’m+am’,m’)=1$ //加上另一个数的若干倍仍互质
        $(am’+a’m,mm’)=1$
      • 所以如果$(n,m)=1,\phi(nm)=\phi(n)*\phi(m)$
    • $phi(p^e)=(p-1)$ $p^{e-1}=p^e(1-1/p) $ p是质数

      • $Prove: [1,p^e]中与p不互质的数的个数为p^e/p=p^{e-1}$
        $\phi(p^e)=p^e-p^{e-1} =p^e*(1-1/p)$
      • 计算公式:$\phi(p)= \prod \phi(p_i^{c_i}) = \prod (p^c_i $ $(1-1/p_i)) = n \prod (1-1/p_i)$
  7. 欧拉定理 如果$(a,m)=1,a^{phi(m)} \equiv 1 \mod m$
    $Prove: $设x取遍m的缩系,则ax取遍m的缩系
    $ \prod x = \prod ax \mod m$
    $\prod x = \prod x *a^{ \phi(m)} \mod m $ //这样的a有phi(m)个
    由于$(x,m)=1$,保证$\prod x $存在模m意义下的逆元
    所以 $a^{ \phi(m)} \equiv 1 \mod m$

  8. 费马小定理 如果$(a,m)=1$,且m是个质数 $a^{m-1} \equiv 1 \mod m $

  9. 扩展欧拉定理 如果$(a,m)!=1 $ 则 $a^b \equiv a^{min(b,b \% \phi(m)+\phi(m))} \mod m$


  10. 如果(a,m)那么最小的正整数使得$a^{x} \equiv 1 \mod m$,x称为a模m的阶
    性质:$x|\phi(m)$
    Prove: 咕咕咕

  11. 原根
    如果g在模m的阶是$\phi(m)$,那么称g是模m的原根

  12. 积性函数
    欧拉函数,莫比乌斯函数,除数函数

  13. 狄利克雷卷积

    满足交换律结合律分配律,可用倍增

    $(f$ $g)(n) = \sum_{d|n} f(d)g(n/d)$

    如果f,g是积性函数,f*g也是积性函数

    $f*e=f$ 单位元:e $e(1)=1$,其他$e(i)=0$;

  14. 莫比乌斯函数
    $e(n)=\sum_{d|n}\mu(d)$

    Prove:转化为二项式系数后转化

    性质: $e(n)=\mu(n)*1$

  15. 莫比乌斯反演

    若$f(n)=\sum_{d|n} g(d)$

    则$g(n)=\sum_{d|n} \mu(d) f(n/d)$

    $Prove:$

    $f = g1$ $\mu1 = e$

    $f $$\mu = g $ 1$ * \mu$

    $f\mu$ $= ge$

    $g=f*\mu $ -> $g(n)= \sum_{d|n} \mu(d) f(n/d)$

$\sum_{i=0}^N C^i_n =2^n $
$\sum_{i=0}^N C(i,x)=C^{x+1}_{n+1}$ 图像证明 竖列的组合数

$\sum_{i=0}^N C^i_{k+i} = C^N_{k+N+1}$ 图像证明 斜列的组合数

$\sum_{i=0}^m C^i_m C^{m-i}_{n-m}=C^m_n$ 组合意义