fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. long long oo=1e18;
  6.  
  7. map<long long,long long> M;
  8. vector<pair<pair<long long,long long>,pair<long long,long long> > > R;
  9.  
  10. long long D(long long a1,long long a2,long long b1,long long b2) {
  11.     if (a1*b1==a2*b2){
  12.         R.push_back(make_pair(make_pair(a1,b1),make_pair(a2,b2)));
  13.         return 0;
  14.     }
  15.     if(M.count(a1*b1-a2*b2))
  16.         return M[a1*b1-a2*b2];
  17.     long long mn=oo;
  18.     if(a1*b1>a2*b2) {
  19.         if((a1%2==0)&&(b1%2!=0))
  20.             mn=min(mn,1+D(a1/2,a2,b1,b2));
  21.         if((a1%3==0)&&(b1%3!=0))
  22.             mn=min(mn,1+D(2*a1/3,a2,b1,b2));
  23.         if((a1%2!=0)&&(b1%2==0))
  24.             mn=min(mn,1+D(a1,a2,b1/2,b2));
  25.         if((a1%3!=0)&&(b1%3==0))
  26.             mn=min(mn,1+D(a1,a2,2*b1/3,b2));
  27.         if((a1%2==0)&&(b1%2==0))
  28.             mn=min(mn,1+min(D(a1/2,a2,b1,b2),D(a1,a2,b1/2,b2)));
  29.         if((a1%3==0)&&(b1%3==0))
  30.             mn=min(mn,1+min(D(2*a1/3,a2,b1,b2),D(a1,a2,2*b1/3,b2)));
  31.         if((a1%2==0)&&(b1%3==0))
  32.             mn=min(mn,1+min(D(a1/2,a2,b1,b2),D(a1,a2,2*b1/3,b2)));
  33.         if((a1%3==0)&&(b1%2==0))
  34.             mn=min(mn,1+min(D(2*a1/3,a2,b1,b2),D(a1,a2,b1/2,b2)));
  35.         if(mn<oo)
  36.             return M[a1*b1-a2*b2]=mn;
  37.         return M[a1*b1-a2*b2]=-oo;
  38.     } else {
  39.         if((a2%2==0)&&(b2%2!=0))
  40.             mn=min(mn,1+D(a1,a2/2,b1,b2));
  41.         if((a2%3==0)&&(b2%3!=0))
  42.             mn=min(mn,1+D(a1,2*a2/3,b1,b2));
  43.         if((a2%2!=0)&&(b2%2==0))
  44.             mn=min(mn,1+D(a1,a2,b1,b2/2));
  45.         if((a2%3!=0)&&(b2%3==0))
  46.             mn=min(mn,1+D(a1,a2,b1,2*b2/3));
  47.         if((a2%2==0)&&(b2%2==0))
  48.             mn=min(mn,1+min(D(a1,a2/2,b1,b2),D(a1,a2,b1,b2/2)));
  49.         if((a2%3==0)&&(b2%3==0))
  50.             mn=min(mn,1+min(D(a1,2*a2/3,b1,b2),D(a1,a2,b1,2*b2/3)));
  51.         if((a2%2==0)&&(b2%3==0))
  52.             mn=min(mn,1+min(D(a1,a2/2,b1,b2),D(a1,a2,b1,2*b2/3)));
  53.         if((a2%3==0)&&(b2%2==0))
  54.             mn=min(mn,1+min(D(a1,2*a2/3,b1,b2),D(a1,a2,b1,b2/2)));
  55.         if(mn<oo)
  56.             return M[a1*b1-a2*b2]=mn;
  57.         return M[a1*b1-a2*b2]=-oo;
  58.     }
  59. }
  60.  
  61. int main() {
  62.     long long a1,b1,a2,b2;
  63.     cin>>a1>>b1>>a2>>b2;
  64.     long long r=D(a1,a2,b1,b2);
  65.     if(r<0)
  66.         cout<<-1<<endl;
  67.     else {
  68.         cout<<r<<endl;
  69.         long long mx=0;
  70.         for(size_t i(0);i<R.size();++i)
  71.             if(R[i].first.first*R[i].first.second>mx){
  72.                 a1=R[i].first.first;
  73.                 b1=R[i].first.second;
  74.                 a2=R[i].second.first;
  75.                 b2=R[i].second.second;
  76.                 mx=a1*b1;
  77.             }
  78.         cout<<a1<<" "<<b1<<endl<<a2<<" "<<b2<<endl;
  79.     }
  80.     return 0;
  81. }
  82.  
Success #stdin #stdout 0s 3440KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
-1
https://ideone.com/0AzRks
language:
C++14 (gcc 8.3)
created:
9 years ago
visibility:
secret

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!