前言

数论在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. 狄利克雷卷积

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

    $(fg)(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$ 组合意义