fork(11) download 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define debug(...)   printf( __VA_ARGS__ )
  4. //#define debug(...)   /****nothing****/
  5. #define pb push_back
  6. #define mp make_pair
  7. #define LL long long
  8. #define resett(arr,val,N) for(int ii=0;ii<(N);ii++) arr[ii]=val;
  9. #define PI 2*acos(0.0)
  10.  
  11. long long extendedEuclid(long long int a, long long int b,long long &x,long long &y) {
  12.     if(a == 0) {
  13.         x = 0;
  14.         y = 1;
  15.         return b;
  16.     }
  17.  
  18.     long long int x1, y1;
  19.  
  20.     long long ret=extendedEuclid(b % a, a, x1,y1);
  21.  
  22.     x = y1 - b/a*x1;
  23.     y=x1;
  24.  
  25.     return ret;
  26. }
  27.  
  28.  
  29. int main() {
  30.  
  31.     LL n,a,b,x,y;
  32.  
  33.     while(cin>>n>>a>>b) {
  34.  
  35.         LL gc=extendedEuclid(a,b,x,y);  // gc= gcd(a,b)
  36.  
  37. //        cout<<gc<<" "<<x<<" "<<y<<endl;
  38.  
  39.         if(n%gc!=0)
  40.             printf("-1\n");
  41.         else {
  42.  
  43.             x=x*n/gc;
  44.             y=y*n/gc;
  45.  
  46. //            cout<<x<<" "<<y<<endl;
  47.  
  48.             LL k1=ceil((long double)-x*gc/b), k2=y*gc/a;
  49.  
  50. //            cout<<k1<<" "<<k2<<endl;
  51. //                k1++;
  52.             x=x+k1*b/gc;
  53.             y=y-k1*a/gc;
  54.  
  55.             if(x<0 || y<0)
  56.                 printf("-1\n");
  57.             else
  58.              printf("%lld %lld\n",x,y);
  59. //            if(a*x+b*y==n)
  60. //                printf("yes\n");
  61.  
  62.  
  63.         }
  64.  
  65.  
  66.  
  67.     }
  68.  
  69.  
  70.     return 0;
  71. }
  72.  
  73.  
  74.  
  75.  
Success #stdin #stdout 0s 4220KB
comments (?)
stdin 
2500000000 25 73789
stdout 
15905 33875
https://ideone.com/6fzPLF
language:
C++14 (gcc 8.3)
created:
6 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!