首页 > 代码库 > 【hdu1576】A/B——扩展欧几里得算法
【hdu1576】A/B——扩展欧几里得算法
扩展欧几里得的模板题,要记住:
x=y1;
y=x1-a/b*y1。
这道题的推导过程如下:
1.因为A/B==0,所以令A/B=x,即A=Bx。又因为n=A%m,所以m*y+n=A。
由上面可推导出Bx-my=n。
2.由扩展欧几里得算法可以算出B*x1+m*y1=1的根,等式两边同时乘上n可以变形为B*(x1*n)-m*(-n*y1)=n。
所以x=n*x1。到这里我们只需要通过扩欧算出x1,答案即为(x1*n)%m。
3.最后要注意的一点,扩展欧几里得算法算出的x1可能为负数,这显然是不成立的。又因为
x=x1+b*t;
y=y1-a*t;
所以x1的值可以写成(x%m+m)%m。这样的话负数也转成了正数,就可以输出答案啦!
具体细节看代码:
#include<cstdio> const int m=9973; using namespace std; void e_gcd(int a,int b,int &x,int &y) { if(b==0) { x=1;y=0;return; } e_gcd(b,a%b,x,y); int t=y; y=x-a/b*y; x=t; } int main() { int t,n,b,x,y; scanf("%d",&t); while(t--) { scanf("%d %d",&n,&b); e_gcd(b,m,x,y); x=(x%m+m)%m; printf("%d\n",x*n%m); } return 0; }
【hdu1576】A/B——扩展欧几里得算法
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。