fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define tw() int t;   cin >> t;  while (t--)
  4. #define ll long long
  5. #define pb push_back
  6. #define vi vector<int>
  7. #define vc vector<char>
  8. #define vs vector<string>
  9. #define pii pair<int, int>
  10. #define vpii vector<pii>
  11. #define mii unordered_map<int, int>
  12. #define mci map<char, int>
  13. #define msi map<string, int>
  14. #define si set<int>
  15. #define sc set<char>
  16. #define ss set<string>
  17. #define all(x) x.begin(), x.end()
  18. #define allcmp(x) x.begin(), x.end(), cmp
  19. const int MOD = 1000000007;
  20.  
  21. vi arr[1000000];
  22. mii map1;
  23. int bfs(int n, int m)
  24. {
  25.     queue<int> q;
  26.     q.push(map1[n]);
  27.     mii dis;
  28.     mii visited;
  29.     dis[map1[n]] = 0;
  30.     while (!q.empty())
  31.     {
  32.         int x = q.front();
  33.         q.pop();
  34.         visited[x] = 1;
  35.         for (auto u : arr[x])
  36.         {
  37.             if (visited[u] == 0)
  38.             {
  39.                 q.push(u);
  40.                 dis[u] += dis[x] + 1;
  41.                 if (u == map1[m])
  42.                   return  dis[u];
  43.             }
  44.         }
  45.     }
  46.     return 0;
  47. }
  48. int32_t main()
  49. {
  50.     ios_base::sync_with_stdio(0);
  51.     cin.tie(0);
  52.     cout.tie(0);
  53.  
  54.     int n1, m1;
  55.     cin >> n1 >> m1;
  56.     int n = n1, m = m1;
  57.  
  58.     int c = 1;
  59.     map1[n] = c;
  60.     while (n != 1)
  61.     {
  62.         int mex = 1;
  63.         for (int i = 1; i <= n / 2; i++)
  64.         {
  65.             if (n % i == 0)
  66.                 mex = max(mex, i);
  67.         }
  68.         c++;
  69.         map1[mex] = c;
  70.  
  71.         arr[map1[n]].pb(map1[mex]);
  72.         arr[map1[mex]].pb(map1[n]);
  73.         n = mex;
  74.     }
  75.  
  76.     if (!map1[m])
  77.     {
  78.         c++;
  79.         map1[m] = c;
  80.     }
  81.     while (m != 1)
  82.     {
  83.         int mex = 1;
  84.         for (int i = 1; i <= m / 2; i++)
  85.         {
  86.             if (m % i == 0)
  87.                 mex = max(mex, i);
  88.         }
  89.  
  90.         if (!map1[mex])
  91.         {
  92.             c++;
  93.             map1[mex] = c;
  94.         }
  95.  
  96.         arr[map1[m]].pb(map1[mex]);
  97.         arr[map1[mex]].pb(map1[m]);
  98.         m = mex;
  99.     }
  100.  
  101.    cout<< bfs(n1, m1);
  102.  
  103.  
  104.     return 0;
  105. }
Success #stdin #stdout 0.02s 27036KB
comments (?)
stdin
copy 
15689 28
stdout
copy 
5
https://ideone.com/hzFN0v
language:
C++14 (gcc 8.3)
created:
5 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!