题目学习——HDUOJ-2669

题目学习——HDUOJ-2669 2022-07-09 879

Romantic

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)

Problem Description Problem Description

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.
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 Input

The input contains multiple test cases.
Each case two nonnegative integer a,b (0<a, b<=2^31)
The input contains multiple test cases. Each case two nonnegative integer a,b (0

Output 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.
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 Sample Input

77 51
10 44
34 79

77 51 10 44 34 79

Sample Output Sample Output

2 -3
sorry
7 -3

2 -3 sorry 7 -3

Author Author

yifenfei yifenfei

#include <iostream>
#include <cstdio>
#define LL long long int
using namespace std;

LL e_gcd(LL a,LL b,LL &x,LL &y)
{
    if(b==0){
        x=1;
        y=0;
        return a;
    }
    LL ans=e_gcd(b,a%b,x,y);
    LL temp=x;
    x=y;
    y=temp-a/b*y;
    return ans;
}
LL inv(LL a,LL m,LL c)
{
    LL x,y;
    LL gcd=e_gcd(a,m,x,y);
    if(c%gcd!=0)return -1;
    m=c/gcd*m;
    if(m<0)m=-m;
    LL ans=x%m;
    if(ans<=0)ans=ans+m;
    return ans;
}


int main()
{
    LL a,b,x,y,ans;
    while(scanf("%lld%lld",&a,&b)!=EOF){
        if((ans=inv(a,b,1))!=-1)printf("%lld %lld
",ans,(1-ans*a)/b);
        else printf("sorry
");
    }
    return 0;
}

文章来自:IT技术分享网
分享地址:http://www.5ityx.cn/cate117/67593.html

上一篇：通过多线程提高代码的执行效率例子

下一篇：为你推荐10款开发常用的代码编辑器

题目学习——HDUOJ-2669

Romantic

题目学习——HDUOJ-2669 相关内容

聚合标签