fork(7) download
copy 
  1. //include
  2. //------------------------------------------
  3. #include <vector>
  4. #include <list>
  5. #include <map>
  6. #include <set>
  7. #include <deque>
  8. #include <queue>
  9. #include <stack>
  10. #include <bitset>
  11. #include <algorithm>
  12. #include <functional>
  13. #include <numeric>
  14. #include <utility>
  15. #include <sstream>
  16. #include <iostream>
  17. #include <iomanip>
  18. #include <cstdio>
  19. #include <cmath>
  20. #include <cstdlib>
  21. #include <cctype>
  22. #include <string>
  23. #include <cstring>
  24. #include <ctime>
  25. #include <iterator>
  26. #include <unordered_map>
  27. #include <unordered_set>
  28. #include <tuple> 
  29. #include <random>
  30. #include <cassert>
  31. using namespace std;
  32. typedef long long ll;
  33.  
  34. #define FOR(i,a,b) for(long long i=(a);i<(b);++i)
  35. #define rep(i,n)  FOR(i,0,n)
  36.  
  37. using Weight = int;
  38. using Flow = int;
  39. struct Edge {
  40.     int src, dst;
  41.     Weight weight;
  42.     Flow cap;
  43.     Edge() : src(0), dst(0), weight(0) {}
  44.     Edge(int s, int d, Weight w) : src(s), dst(d), weight(w) {}
  45. };
  46. using Edges = std::vector<Edge>;
  47. using Graph = std::vector<Edges>;
  48. using Array = std::vector<Weight>;
  49. using Matrix = std::vector<Array>;
  50.  
  51. void add_edge(Graph &g, int a, int b, Weight w = 1) {
  52.     g[a].emplace_back(a, b, w);
  53.     g[b].emplace_back(b, a, w);
  54. }
  55. void add_arc(Graph &g, int a, int b, Weight w = 1) { g[a].emplace_back(a, b, w); }
  56.  
  57. std::vector<Weight> dijkstra(const Graph &g, int s) {
  58.     const Weight INF = std::numeric_limits<Weight>::max() / 8;
  59.     using state = std::tuple<Weight, int>;
  60.     std::priority_queue<state> q;
  61.     std::vector<Weight> dist(g.size(), INF);
  62.     dist[s] = 0;
  63.     q.emplace(0, s);
  64.     while (q.size()) {
  65.         Weight d;
  66.         int v;
  67.         std::tie(d, v) = q.top();
  68.         q.pop();
  69.         d *= -1;
  70.         /* if(v == t) return d; */
  71.         if (dist[v] < d) continue;
  72.         for (auto &e : g[v]) {
  73.             if (dist[e.dst] > dist[v] + e.weight) {
  74.                 dist[e.dst] = dist[v] + e.weight;
  75.                 q.emplace(-dist[e.dst], e.dst);
  76.             }
  77.         }
  78.     }
  79.     return dist;
  80. }
  81.  
  82. std::vector<ll> eratosthenes_sieve(int n) {
  83.     std::vector<ll> ps(n + 1);
  84.     std::iota(ps.begin() + 2, ps.end(), 2);
  85.     for (int i = 2; i * i <= n; ++i)
  86.         if (ps[i])
  87.             for (int j = i * i; j <= n; j += i) ps[j] = 0;
  88.     return ps;
  89. }
  90.  
  91. std::vector<ll> make_primes(int n) {
  92.     std::vector<ll> ps = eratosthenes_sieve(n);
  93.     ps.erase(std::remove(ps.begin(), ps.end(), 0), ps.end());
  94.     return ps;
  95. }
  96. const int N = 100010;
  97. int prime[N];
  98.  
  99. int main() {
  100.     vector <ll> v = make_primes(N);
  101.     Graph g(N + 10);
  102.     for (int i = 1;i <= N;i++) {
  103.         add_arc(g, i - 1, i);
  104.         add_arc(g, i + 1, i);
  105.         ll x = i;
  106.         for (ll j = 0;v[j] * v[j] <= x;j++) {
  107.             if (x%v[j] == 0) {
  108.                 add_arc(g, i / v[j], i);
  109.                 while (x%v[j] == 0)x /= v[j];
  110.             }
  111.         }
  112.     }
  113.     for (int i = 1;i <= v.size();i++) {
  114.         add_arc(g, 1, v[i]);
  115.     }
  116.     vector<int> u = dijkstra(g, 1);
  117.     int T;cin >> T;
  118.     while (T--) {
  119.         int a;cin >> a;
  120.         cout << u[a] << endl;
  121.     }
  122. }
  123.  
Success #stdin #stdout 0.07s 15624KB
comments (?)
stdin
copy 
10
1 2 3 4 5 6 7 8 9 10
stdout
copy 
0
1
1
2
1
2
1
2
2
2
https://ideone.com/pfjMRW
language:
C++ (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!