fork download
copy 
  1. #include <iostream>
  2. #include <fstream>
  3. #include <cmath>
  4. using namespace std;
  5. long long ex_gcd(long long a, long long b, long long *x, long long *y);
  6.  
  7. int main(){
  8.     #ifndef ONLINE_JUDGE
  9.         freopen("input.txt", "r", stdin);
  10.         //freopen("output.txt", "w", stdout);
  11.     #endif
  12.     long long n, c1, c2, n1, n2;
  13.     long long m1, m2, x, y, d, t, t1, t2;
  14.  
  15.     while(cin>>n && n!=0){
  16.         cin>> c1 >> n1 >> c2 >> n2;
  17.         d = ex_gcd(n1, n2, &x, &y);
  18.         if(n%d!=0 || (n<n1 && n<n2) ){
  19.             cout << "failed\n";
  20.             continue;
  21.         }
  22.  
  23.         t1 = ceil(-n*x/n2);
  24.         t2 = floor(n*y/n1);
  25.  
  26.         if(t1>t2){
  27.             cout << "failed\n";
  28.             continue;
  29.         }
  30.         if(c1*n2/d-c2*n1/d>=0)
  31.             t=t1;
  32.         else
  33.             t=t2;
  34.  
  35.         m1 = n*x/d + n2/d*t;
  36.         m2 = n*y/d - n1/d*t;
  37.         cout << m1 << " " << m2 << endl;
  38.     }
  39.     return 0;
  40. }
  41.  
  42. long long ex_gcd(long long a, long long b, long long *x, long long *y){
  43.     long long tmp, r, p, lx, ly, rx, ry, first=1;
  44.     if(a<b)
  45.         return ex_gcd(b, a, y, x);
  46.     else{
  47.         lx=1; ly=0;
  48.         rx=0; ry=1;
  49.         while(b!=0){
  50.             p=a/b; r=a%b;
  51.             a=b; b=r;
  52.             if(b==0 && first){
  53.                 lx=0; ly=1;
  54.                 break;
  55.             }
  56.             if(b>0){
  57.                 first=0;
  58.                 lx -= p*rx; ly -= p*ry;
  59.                 if(a%b!=0){
  60.                     tmp=lx; lx=rx; rx=tmp;
  61.                     tmp=ly; ly=ry; ry=tmp;
  62.                 }
  63.             }
  64.         }
  65.         *x=lx; *y=ly;
  66.         return a;
  67.     }
  68. }
  69.  
Success #stdin #stdout 0.02s 2728KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/eoz4c
language:
C++ (gcc 8.3)
created:
13 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!