• 周五. 10月 7th, 2022

5G编程聚合网

5G时代下一个聚合的编程学习网

热门标签

【数论】拓展欧几里得

admin

11月 28, 2021

今天开始看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 }

发表回复

您的电子邮箱地址不会被公开。