游客 注册 | 登录
中文 | En

3050 - 缘分检测公式

通过次数

0

提交次数

0

时间限制 : 1 秒 内存限制 : 128 MB

       众所周知，Q学长是CCNU的一名优秀的ACMER，卖的一手好萌，已经俘获无数学(FU)妹(NV)芳心，但是

Q学长希望找到一个与他最有缘分的妹纸，因此数学极为优秀的Q学长给出了一个缘分检测公式，希望你检

测一下该学妹是否与Q学长有缘，现在给你这个公式的系数a和b,请你找到一个非负整数X和一个整数Y让它

们满足aX+bY=1这个缘分公式，1代表Q学长能与学妹一生一世在一起，当然如果没能找到符合条件的解，则

直接输出"sorry"表示Q学长与学妹没有缘分。雯神表示“So easy, 妈妈再也不用担心胖纸的学习了”


题目输入

本题包含多组输入，每组输入包含两个非负整数a,b(0<a,b<=2^31)


题目输出

对于每组输入数据输出符合条件的非负整数X和整数Y，如果有多组解，求出的X最小的那组解，无解则输出"sorry"

 

输入/输出样例

输入格式

77 51 
10 44 
34 79

输出格式

2 -3
sorry
7 -3

C++解答

#include<cstdio>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
using namespace std;

long long a,b;
long long x,y;
long long ex_gcd(long long a,long long b,long long &x,long long &y)
{
    if(b==0)
    {
        x=1;
        y=0;
        return a;
    }
    long long tmp,res;
    res=ex_gcd(b,a%b,x,y);
    tmp=x;
    x=y;
    y=tmp-(a/b)*y;
    return res;
}

long long  inv(long long  a,long long  b)
{
    long long  d,x,y;
    d = ex_gcd(a,b,x,y);
    return d == 1 ? (x+b)%b : -1;
}

int main()
{
    //freopen( "A.txt", "r", stdin );
   // freopen( "_A.txt", "w", stdout );
    while(cin>>a>>b)
    {
        long long ans=inv(a,b);
        if(ans==-1)
        {
            cout<<"sorry"<<endl;
        }
        else
        {
            cout<<ans<<" "<<(1-ans*a)/b<<endl;
        }
    }
    return 0;
}
请先登陆