数论模板与典型问题

朴素欧几里得

第三条是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=1bx’+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

于是乎
x=y’ \quad \quad \quad y=x’-\lfloor \frac{a}{b} \rfloor *y’
对于 a,b 有负数的情况,我们需要将他们其中一个负数加上另外一个数直到非负 ,即若$a<0 , b>0,那么 a=a\bmod b+b
即可

如果有两个负数,直接将整个式子反号就可以了 , 对解都不会产生影响

注意 , 用 exgcd 解出的不定方程的 (x,y) 都是 ax+by=1 的解 , 需要在此基础上乘刚才的 c’ 得到 (x_0,y_0)

有解系:
x=x_0+b_r
y=y_0-a_r

埃式筛法预处理 [2,N] 数的最小素因子或质因数的个数

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]++;
    }
}

0 条评论

发表评论

Avatar placeholder

您的电子邮箱地址不会被公开。 必填项已用*标注