1 solutions

  • 0
    @ 2025-11-5 16:06:52

    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;
    }
    
    • 1

    Information

    ID
    17490
    Time
    1000ms
    Memory
    128MiB
    Difficulty
    (None)
    Tags
    # Submissions
    0
    Accepted
    0
    Uploaded By