数论模板与典型问题
朴素欧几里得
第三条是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
于是乎
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 条评论