SHARE
TWEET

NrDiv(#2247)

UnknownPrecentage Jun 25th, 2019 62 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. int st[12], dr[12];
  4. int t[] = {0, 3, 5, 7, 11, 13, 17, 19, 23}, c[] = {0, 15, 7, 6, 4, 2, 2, 2, 2};
  5. int n, nrdiv, x;
  6. long long  nrimp = 2000000000;
  7. int NrDiv(int x)
  8. {
  9.     int fm = 0;
  10.     while(x % 2 == 0) {fm++;x /= 2;}
  11.     int nrd = fm + 1;int d = 3;
  12.     while(d * d <= x)
  13.     {
  14.         fm = 0;
  15.         while(x % d == 0) {fm++;x /= d;}
  16.         if(fm) nrd *= (fm + 1);
  17.         d += 2;
  18.     }
  19.     if(x != 1) nrd *= 2;
  20.     return nrd;
  21. }
  22. bool ok(int top)
  23. {
  24.     dr[top] = dr[top - 1] * (1 + st[top]);
  25.     if(dr[top] <= nrdiv) return 1;
  26.     return 0;
  27. }
  28. int pow(int a, int k)
  29. {
  30.     int i, p = 1;
  31.     for(i = 1;i <= k;i++) p *= a;
  32.     return p;
  33. }
  34. void sol(int top)
  35. {
  36.     int i;
  37.     long long w = 1;
  38.     for(i = 1;i <= top;i++) w *= pow(t[i], st[i]);
  39.     nrimp = min(nrimp, w);
  40. }
  41. void backtraking()
  42. {
  43.     bool cand;
  44.     int top = 1;
  45.     dr[0] = 1;
  46.     while(top)
  47.     {
  48.         cand = 0;
  49.         while(!cand && st[top] < c[top])
  50.         {
  51.             st[top]++;
  52.             cand = ok(top);
  53.         }
  54.         if(!cand) top--;
  55.         else if(dr[top] == nrdiv) sol(top);
  56.         else if(top < 8) st[++top] = 0;
  57.     }
  58. }
  59. int main()
  60. {
  61.     cin >> n;
  62.     nrdiv = NrDiv(n);
  63.     backtraking();
  64.     cout << nrimp;
  65. }
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