数论模板与典型问题(不断完善ing)
数论模板与典型问题
朴素欧几里得
第三条是CF上看见的的一个有意思的结论
\gcd(a,b)=\gcd(a,b-a)
\gcd(a,b,c)=\gcd(a,\gcd(b,c))=\gcd(\gcd(a,b),c)
第三条的应用 : CF1459C
扩展欧几里得
对于三个自然数 a,b,c , 求解ax+by=c 的 (x,y) 的整数解
整数解存在的充分条件为
\gcd(a,b) | c
算出 \gcd 后 , (a,b,c) 分别除以 \gcd ,原式转化为
a'x+b'y=c' \quad a⊥b\quad(a与b互质)
此时仍将 a' 记作 a , 将 b' 记作 b ,