SHARE
TWEET

Untitled

a guest May 19th, 2019 66 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <math.h>
  3. #include <vector>
  4. #include <unordered_map>
  5.  
  6. using namespace std;
  7. int minSteps;
  8. vector<int> getPrimes(int a) {
  9.     vector<int> vec;
  10.     for (int i = 2; a > 1; ++i)  {
  11.         while (a % i == 0) {  
  12.             if (vec.empty() || vec.back() != i) {
  13.                 vec.push_back(i);
  14.             }
  15.             a /= i;  
  16.         }
  17.     }
  18.     return vec;
  19.     //m[a] = vec;
  20. }
  21.  
  22. //unordered_map <int,vector<int>> m;
  23.  
  24. void addX (int A, int B, int steps) {
  25.         //cout << A << " " << B << " " << steps << endl;
  26.         vector<int> vec;
  27.         if (A == B && steps < minSteps) {
  28.             minSteps = steps;
  29.             return;
  30.         }
  31.         if (A > B) {
  32.             return;
  33.         }
  34.         if (A < 2) {
  35.             return;
  36.         }
  37.         //if(m.find(A) ==  unordered_map::end){
  38.             vec = getPrimes(A);
  39.         //}
  40.         // vector<int> vec = getPrimes(A);
  41.         ++steps;
  42.         for (int i = 0; i < vec.size(); ++i) {
  43.             //addX(A + m[A][i], B, steps);
  44.             addX(A + vec[i], B, steps);
  45.         }
  46.     }
  47. int main() {
  48.     int A, B;
  49.     cin >> A >> B;
  50.     int count = 0, steps;
  51.     while (A != 0 || B != 0) {
  52.         minSteps = 1000;
  53.         count++;
  54.         steps = 0;
  55.         addX (A, B, 0);
  56.         if (minSteps == 1000) {
  57.             minSteps = -1;
  58.         }
  59.         cout << "Case " << count << ": " << minSteps << endl;
  60.         cin >> A >> B;    
  61.     }
  62. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top