fork download
copy 
  1. /* Team name: Omega
  2. *  Problem name: Template
  3. */
  4. #include <vector>
  5. #include <list>
  6. #include <map>
  7. #include <set>
  8. #include <queue>
  9. #include <deque>
  10. #include <stack>
  11. #include <bitset>
  12. #include <algorithm>
  13. #include <functional>
  14. #include <numeric>
  15. #include <utility>
  16. #include <sstream>
  17. #include <iostream>
  18. #include <iomanip>
  19. #include <cstdio>
  20. #include <cmath>
  21. #include <cstdlib>
  22. #include <ctime>
  23. #include <cstring>
  24.  
  25. using namespace std;
  26.  
  27. #define SZ(a) int((a).size())
  28. #define PB push_back
  29. #define ALL(c) (c).begin(),(c).end()
  30. #define LLA(A) A.rbegin(), A.rend()
  31. #define CPY(A, B) memcpy(A, B, sizeof(A))
  32. #define BSC(A, x) (lower_bound(ALL(A), x) - A.begin())
  33. #define PRESENT(c,x) ((c).find(x) != (c).end())
  34. #define CPRESENT(c,x) (find(all(c),x) != (c).end()) // present in a container or not.
  35. #define MP make_pair
  36. #define REP(i,n) for(int _n=n, i=0;i<_n;++i)
  37. #define REP1(i,n) for(int _n=n, i=1;i<=_n;++i)
  38. #define FOR(i,a,b) for(int i=(a),_b=(b);i<_b;++i)
  39. #define FOREACH(it,c) for(typeof((c).begin()) it=(c).begin();it!=(c).end();++it)
  40. #define FF first
  41. #define SS second
  42. #define INPUT(a) freopen (a, "r", stdin)
  43. #define OUTPUT(a) freopen (a, "w", stdout)
  44. #define FORD(i, b, a) for (int i=int(b-1);i>=int(a);--i)
  45. #define FILL(a, v) memset(a, v, sizeof(a));
  46. #define DREP(a)                 sort(ALL(a)); a.erase(unique(ALL(a)),a.end()) // will make the vector unique and sorted order
  47. #define DEBUG(args...)          {dbg,args; cerr<<endl;}
  48. #define INF                     (int)1e9
  49. #define LINF                    (long long)1e18
  50.  
  51. typedef long long LL;
  52. typedef long double LD;
  53. typedef vector <int> VI;
  54. typedef vector <LL> VLL;
  55. typedef vector <double> VD;
  56. typedef vector<string> VS;
  57. typedef vector <VI> VVI;
  58. typedef pair <int,int> PII;
  59. typedef pair <LL,LL> PLL;
  60. typedef vector <PII > VPII;
  61. typedef pair <double, double> PDD;
  62. typedef vector <PDD> VPDD;
  63.  
  64. struct debugger { template<typename T> debugger& operator , (const T& v) {  cerr<<v<<" ";    return *this;  } } dbg;
  65.  
  66. template<class T> string i2s(T x) {ostringstream o; o << x; return o.str(); }
  67. VS splt(string s, char c = ' ') {VS rv; int p = 0, np; while (np = s.find(c, p), np >= 0) {if (np != p) rv.PB(s.substr(p, np - p)); p = np + 1;} if (p < SZ(s)) rv.PB(s.substr(p)); return rv;}
  68.  
  69. void print(VI v, int sz = -1) { if (sz == -1) sz = SZ(v); cerr << "["; if (sz) cerr << v[0]; FOR (i, 1, sz) cerr << ", " << v[i]; cerr << "]" << endl; }
  70. void print(VD v, int sz = -1) { if (sz == -1) sz = SZ(v); cerr << "["; if (sz) cerr << v[0]; FOR (i, 1, sz) cerr << ", " << v[i]; cerr << "]" << endl; }
  71. void print(VS v, int sz = -1) { if (sz == -1) sz = SZ(v); cerr << "["; if (sz) cerr << v[0]; FOR (i, 1, sz) cerr << ", " << v[i]; cerr << "]" << endl; }
  72. void print (PII v) { cerr << "{ " << v.FF << ", " << v.SS << " }"; }
  73. void print (VPII v, int sz = -1) { if (sz == -1) sz = SZ(v); cerr << "[ "; if (sz) print (v[0]); FOR (i, 1, sz) { cerr << ", "; print (v[i]);} cerr << "]" << endl;}
  74. void print(VVI v, int sz1 = -1, int sz2 = -1) { if (sz1 == -1) sz1 = SZ(v); if (sz2 == -1) sz2 = SZ(v[0]); cerr << "[ ---" << endl;if (sz1) cerr << " ", print(v[0], sz2);FOR(i, 1, sz1) cerr << " ", print(v[i], sz2);    cerr << "--- ]\n";}
  75.  
  76. const double EPS = 1e-9;
  77. const int MOD = int(1e9) + 7;
  78. const double PI = acos(-1.0); //M_PI;
  79. // Asy psyho says : Algo is more about pyschology and ability to stay focused during short amount of time.
  80. //////////////////////////////////////////////////////////////////////////////////////////////////////////// 
  81. //                                                                              Main Code Starts Now                                                                                        //
  82. ////////////////////////////////////////////////////////////////////////////////////////////////////////////
  83. int gcd (int a, int b) {
  84.     return b > 0 ? gcd (b, a % b) : a;
  85. }
  86.  
  87. const int N = 794898;
  88. bool prime[N + 5];
  89. vector <vector <int > > divi (N + 5);
  90. bool visited[N + 5];
  91.  
  92. void sieve () {
  93.     FOR (i, 2, N + 1) {
  94.         prime[i] = true;
  95.     }
  96.     for (int i = 2; i * i <= N; i++)
  97.         if (prime[i]) {
  98.             for (int j = i + i; j <= N; j += i) {
  99.                 prime[j] = false;
  100.             }
  101.         }
  102.     for (int i = 2; i <= N; i++)
  103.         if (prime [i])
  104.             for (int j = i; j <= N; j += i) {
  105.                 if (SZ(divi[j]) == 0) 
  106.                 	divi[j].PB (i);
  107.             }
  108. }
  109.  
  110. int Ans[N];
  111.  
  112. int main() {
  113.     sieve();
  114.  
  115.     vector <set<int> > st (N + 5);
  116.     REP1 (i, N) {
  117.         if (prime[i])
  118.             for (int j = i; j <= N; j += i) {
  119.                 st[i].insert (j);
  120.             }
  121.     }
  122.  
  123.     VI a;
  124.     a.PB (1);
  125.     a.PB (2);
  126.     visited[2] = true;
  127.  
  128.     set <int> :: iterator it;
  129.     REP (i, N) {
  130.         int num = a[SZ(a) - 1];
  131.         int mn = N, pos = 0;
  132.         REP (j, SZ(divi[num])) {
  133.             int temp = divi[num][j];
  134.             VI toRemove;
  135.             int ok = false;
  136.             for (it = st[temp].begin(); it != st[temp].end(); it++) {
  137.                 if (*it % temp == 0) {
  138.                     if (visited[*it]) {
  139.                         toRemove.PB (*it);
  140.                     } else {
  141.                         //toRemove.PB (*it);
  142.                         //a.PB (*it);
  143.                         ok = true;
  144.                         if (*it < mn) {
  145.                             mn = *it;
  146.                             pos = temp;
  147.                         }
  148.                         //visited[*it] = true;
  149.                         break;
  150.                     }
  151.                 }               
  152.             }   
  153.             REP (k, SZ(toRemove)) {
  154.                 st[temp].erase (toRemove[k]);
  155.             }
  156.         }
  157.         a.PB (mn);
  158.         st[pos].erase (mn);
  159.         visited[mn] = true;
  160.     }
  161.  
  162.  
  163.  
  164.     REP (i, SZ(a)) {
  165.         Ans[a[i]] = i + 1;
  166.     }
  167.  
  168.     //cout << *max_element (Ans, Ans + 300000) << endl;
  169.  
  170.     //print (a, 25);
  171.  
  172.     int n;
  173.     while (1) {
  174.         scanf ("%d", &n);
  175.         if (n == 0) break;
  176.         printf ("The number %d appears in location %d.\n", n, Ans[n]);
  177.     }
  178.  
  179.  
  180.  
  181.     return 0;
  182. }
Success #stdin #stdout 0.87s 73344KB
comments (?)
stdin
copy 
12
21
2
33
100000
299977
0
stdout
copy 
The number 12 appears in location 7.
The number 21 appears in location 0.
The number 2 appears in location 2.
The number 33 appears in location 0.
The number 100000 appears in location 50001.
The number 299977 appears in location 0.
https://ideone.com/YqhwZV
language:
C++ (gcc 8.3)
created:
10 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!