[数论]拓展欧几里得
今天开始看orz数论了 数论一直是我最弱的一项 (一学数论就想睡觉啊啊TAT .zZ)从初三到现在每年都有学 每年都忘 于是乎做一个总结 希望能掌握神奇的数论
去年noip就考了拓展欧几里得的模板题 因为不会 送了100分- -
拓展欧几里得说简单了其实就是 给出方程ax+by=gcd(a,b) 求解(x,y)
有学过快速求gcd的都知道 gcd(a,b)=gcd(b,a%b) 我们可以用这个性质求解
假设已经知道bx+(a%b)y=gcd(b,a%b)的解(x,y)
bx+(a%b)y=gcd(b,a%b)
->bx+(a%b)y=gcd(a,b)
->bx+(a-a/b*b)y=gcd(a,