nyoj 正数性质

整数性质

时间限制:500 ms  |  内存限制:65535 KB
难度:1
 
描述

我们知道,在数学中,对于任意两个正整数a和b,必定存在一对整数s、t使得sa+tb=gcd(a,b)。

 
输入
多组测试数据。
每组数据输入两个非负整数a和b且a+b>0且a不等于b。
其中0<=a,b<100000。
输出
输出满足条件的 s 和 t 。
样例输入
2 4
3 8
737 635
样例输出
1 0
3 -1
193 -224
提示

运用欧几里得定理求得的才是正确答案。

http://baike.sogou.com/v5706906.htm?fromTitle=扩展欧几里德算法

看完之后就明白了

#include <stdio.h>
#include <math.h>

void extends_Gcd(int a,int b,int &s,int &t)
{
if(!b)
{
s=1;
t=0;
return ;
}

extends_Gcd(b,a%b,s,t);
int temp=s;
s=t;
t=temp-a/b*t;

}

int main()
{
int a,b;
while(~scanf("%d%d",&a,&b))
{
int s=0,t=0;
extends_Gcd(a,b,s,t);
printf("%d %d\n",s,t);
}
return 0;
}

不要用cin cout 会超时。。

上一篇:父页面与iframe、父页面与子页面的通讯


下一篇:Docker学习笔记之-在CentOS中安装Docker