整数性质 时间限制：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
-
代码:
#include
void EXGCD(int a,int b,int &x,int &y)
{
if(b==0)
{
x=1;
y=0;
return ;
}
EXGCD(b,a%b,x,y);
int tem;
tem=x;
x=y;
y=tem-a/b*y;
}
int main()
{
int a,b,x,y;
while(~scanf("%d%d",&a,&b))
{
EXGCD(a,b,x,y);
printf("%d %d\n",x,y);
}
return 0;
}
<script type="text/java script">
-
<script type="text/java script">BAIDU_CLB_fillSlot("771048");
-
点击复制链接 与好友分享!
回本站首页
<script>
function copyToClipBoard(){
var clipBoardContent=document.title + '\r\n' + document.location;
clipBoardContent+='\r\n';
window.clipboardData.setData("Text",clipBoardContent);
alert("恭喜您！复制成功");
}
<script>window._bd_share_config={"common":{"bdSnsKey":{},"bdText":"","bdMini":"2","bdMiniList":false,"bdPic":"","bdStyle":"0","bdSize":"24"},"share":{}};with(document)0[(getElementsByTagName('head')[0]||body).appendChild(createElement('script')).src='http://bdimg.share.baidu.com/static/api/js/share.js?v=89860593.js?cdnversion='+~(-new Date()/36e5)];
|