今天开始看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,b)
->ay+b(x-a/b*y)=gcd(a,b)
于是可以得到新的x’=y,y’=(x-a/b*y)
递归求解即可
代码：
1 int extgcd(int a,int b,int &x,int &y){ 2 if (!b){ 3 x=1,y=0; 4 return a; 5 }else{ 6 int res=extgcd(b,a%b,x,y); 7 int t=x; 8 x=y,y=t-a/b*y; 9 return res; 10 } 11 }