fork download
copy 
  1. // https://r...content-available-to-author-only...t.com/likecs/Codechef-June-18-/master/work_ways.cpp
  2. #include <bits/stdc++.h>
  3. using namespace std;
  4.  
  5. int n, c, ptr;
  6. vector<int> facts;
  7. int ans[1000001];
  8.  
  9. bool check(int idx) {
  10.   ptr = n;
  11.   int prod = c;
  12.   while(ptr > 0) {
  13.     while(prod % facts[idx] != 0) {
  14.       idx -= 1;
  15.     }
  16.     prod /= facts[idx];
  17.     ans[ptr] = facts[idx] + ptr - 1;
  18.     ptr -= 1;
  19.     if (idx != (facts.size() - 1) && facts[idx] == (facts[idx + 1] - 1)) {
  20.       // greedily chose the largest factor.
  21.       idx += 1;
  22.     }
  23.     if (idx == 0 || prod == 1) {
  24.       // string of 1 as factor so prod will remain same.
  25.       break;
  26.     }
  27.   }
  28.   return (prod == 1);
  29. }
  30.  
  31. int main() {
  32.   ios_base::sync_with_stdio(false);
  33.   int t;
  34.   cin >> t;
  35.   while(t--) {
  36.     cin >> n >> c;
  37.     facts.clear();
  38.     int x = sqrt(c);
  39.     for(int i = 1; i <= x; ++i) {
  40.       if (c % i == 0) {
  41.         facts.push_back(i);
  42.         if (i * i != c) {
  43.           facts.push_back(c / i);
  44.         }
  45.       }
  46.     }
  47.     sort(facts.begin(), facts.end());
  48.     for(int i = 0; i < facts.size(); ++i) {
  49.       if (check(i)) {
  50.         break;
  51.       }
  52.     }
  53.     for(int i = 1; i <= ptr; ++i) {
  54.       cout << i << " ";
  55.     }
  56.     for(int i = ptr+1; i <= n; ++i) {
  57.       cout << ans[i] << " ";
  58.     }
  59.     cout << "\n";
  60.   }
  61.   return 0;
  62. }
Success #stdin #stdout 0s 4552KB
comments (?)
stdin
copy 
9
4 221760
4 2882880
4 294053760
4 367567200
5 21621600
5 32432400
5 367567200
5 551350800
5 698377680
stdout
copy 
15 23 26 31 
35 40 46 51 
117 133 138 143 
119 144 146 153 
20 27 35 39 39 
18 34 37 43 43 
34 53 57 63 67 
34 61 65 69 69 
38 64 67 69 72
https://ideone.com/ofZ3yB
language:
C++ (gcc 8.3)
created:
5 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!