hdu 2669 Romantic 扩展欧几里得-白红宇的个人博客

hdu 2669 Romantic 扩展欧几里得

发布日期：2021-05-09 04:21:32 浏览次数：16 分类：博客文章

本文共 940 字，大约阅读时间需要 3 分钟。

Now tell you two nonnegative integer a and b. Find the nonnegative integer X and integer Y to

satisfy X*a + Y*b = 1. If no such answer print "sorry" instead.

Input

The input contains multiple test cases.

Each case two nonnegative integer a,b (0<a, b<=2^31)

Output

output nonnegative integer X and integer Y, if there are more answers than the X smaller one

will be choosed. If no answer put "sorry" instead.

Sample Input

77 51

10 44

34 79

Sample Output

2 -3

sorry

7 -3

思路：exgcd 最后X为最小正解

代码：

1 #include 
     
       2 using namespace std; 3 typedef long long ll; 4 ll exgcd(ll a, ll b, ll &x, ll &y) { 5     if(!b) { 6         x=1;y=0;return a; 7     } 8     ll ans=exgcd(b,a%b,x,y); 9     ll temp=x;10     x=y;11     y=temp-a/b*y;12     return ans;13 }14 int main() {15     ios::sync_with_stdio(false);16     ll a,b,x,y;17     while(cin>>a>>b) {18         ll g=exgcd(a,b,x,y);19         if(g!=1) {20             cout<<"sorry"<

View Code

上一篇：51Nod 1352 集合计数扩展欧几里得

下一篇：51Nod 1256 乘法逆元扩展欧几里得

发表评论

关于作者

喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！

-- 愿君每日到此一游！

发表评论

最新留言

关于作者

推荐文章