1 solutions
-
0
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