数论模板与典型问题

朴素欧几里得

第三条是CF上看见的的一个有意思的结论

\gcd(a,b)=\gcd(a,b-a)

\gcd(a,b,c)=\gcd(a,\gcd(b,c))=\gcd(\gcd(a,b),c)

\gcd(a_1,a_2,a_3…a_n)=\gcd(a_1,\gcd(a2-a1,a3-a2…a_n-a_{n-1}))

第三条的应用 : CF1459C

扩展欧几里得

问题描述

对于三个自然数 a,b,c , 求解ax+by=c 的 (x,y) 的整数解

Solution

整数解存在的充分条件为
\gcd(a,b) | c

算出 \gcd 后 , (a,b,c) 分别除以 \gcd ,原式转化为
a’x+b’y=c’ \quad a⊥b\quad(a与b互质)
此时仍将 a’ 记作 a , 将 b’ 记作 b , 将 c’ 记作 c

若 a,b 中一数为正 , 将一个数加上另一个数直到为正即可. 若两数为负 , 分别取负转化为正数即可 )

根据朴素欧几里得递归边际得知 , 因为 a⊥b , 最大公因数为 d=1

边际条件为 (d=1,x=1,y=0)

在朴素欧几里得中 \gcd(a,b)=\gcd(b,a\bmod b)

我们令 r=a\bmod b , 有 r=a-\lfloor \frac{a}{b} \rfloor*b

即 \gcd(a,b)=\gcd(b,r)

在这个过程中 不定方程的形式也发生了转化

从 ax+by=1 到 bx’+ry’=1

而递归是从外层到内层 , 我们在边际条件中有 (x=1,y=0) , 就能利用内层的 (x’,y’) 在回溯过程中推导出外层的 (x,y)

也就是说我们要依据 bx’+ry’=1 的 (x’,y’) 推出 ax+by=1 的 (x,y)

在 bx’+ry’=1 的等式两边同时加上 $(\lfloor \frac{a}{b} \rfloorb)y’ , 便可以将r还原成a$ 从而变为外层等式的样子
bx’+(r+\lfloor \frac{a}{b} \rfloor_b)y’=1+(\lfloor \frac{a}{b} \rfloor_b)y’ \quad \to \quad bx’+ay’=1+(\lfloor \frac{a}{b} \rfloor_b)y’
移项
ay’+b(x’-\lfloor \frac {a}{b}\rfloor*y’)=1

int pri_cnt[N];
for(int i = 2; i<N ; ++i){
    if(pri_cnt[i]) continue;
    for(int j = i ; j < N ; j += i){
        pri_cnt[j]++;
    }
}