fork download
copy 
  1. /*
  2.        shool : Cu Chi High School
  3.        participant : Ngo Quoc Binh
  4. */
  5. #include <bits/stdc++.h>
  6. using namespace std;
  7.  
  8. #define debug(x) cerr << #x << " = " << x << "\n";
  9. #define vdebug(a) cerr << #a << " = "; for(auto x : a) cout << x << " "; cout << "\n";
  10. #define TIME cerr << "\nTime elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s\n";
  11. #define fastIO ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  12. #define hashmap unordered_map
  13. #define hashset unordered_set
  14. #define all(x) (x).begin(),(x).end()
  15. #define rall(x) (x).rbegin(),(x).rend()
  16. #define rev(x) reverse(all(x))
  17. #define sz(x) ((int)((x).size()))
  18. #define max_arr(x) *max_element(all(x))
  19. #define min_arr(x) *min_element(all(x))
  20.  
  21. #define pb push_back
  22. #define pf push_front
  23. #define PB pop_back
  24. #define PF pop_front
  25. #define en '\n'
  26. #define ff first
  27. #define ss second
  28. #define task "wtf"
  29.  
  30. using ll = long long;
  31. using ull = unsigned long long;
  32. using ld = long double;
  33. using u128 = __uint128_t;
  34.  
  35. mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
  36.  
  37. ull mul_mod(ull a, ull b, ull mod)
  38. {
  39.         return (u128)a * b % mod;
  40. }
  41.  
  42. ull pow_mod(ull a, ull d, ull mod)
  43. {
  44.         ull res = 1;
  45.         while(d)
  46.         {
  47.                 if(d & 1) res = mul_mod(res, a, mod);
  48.                 a = mul_mod(a, a, mod);
  49.                 d >>= 1;
  50.         }
  51.         return res;
  52. }
  53.  
  54. bool isPrime(ull n)
  55. {
  56.         if(n < 2) return false;
  57.         for(ull p : {2,3,5,7,11,13,17,19,23,29,31,37})
  58.         {
  59.                 if (n % p == 0) return n == p;
  60.         }
  61.  
  62.         ull d = n - 1, s = 0;
  63.         while((d & 1) == 0)
  64.         {
  65.                 d >>= 1;
  66.                 s++;
  67.         }
  68.  
  69.         for(ull a : {2ULL,325ULL,9375ULL,28178ULL,450775ULL,9780504ULL,1795265022ULL})
  70.         {
  71.                 if (a % n == 0) continue;
  72.                 ull x = pow_mod(a, d, n);
  73.                 if (x == 1 || x == n - 1) continue;
  74.                 bool ok = false;
  75.                 for (ull r = 1; r < s; r++) {
  76.                 x = mul_mod(x, x, n);
  77.                 if (x == n - 1) {
  78.                         ok = true;
  79.                         break;
  80.                 }
  81.                 }
  82.                 if (!ok) return false;
  83.         }
  84.         return true;
  85. }
  86.  
  87. ull pollard(ull n) {
  88.     if (n % 2 == 0) return 2;
  89.  
  90.     while(true)
  91.     {
  92.         ull c = uniform_int_distribution<ull>(1, n - 1)(rng);
  93.         ull x = uniform_int_distribution<ull>(0, n - 1)(rng);
  94.         ull y = x;
  95.         ull d = 1;
  96.  
  97.         auto f = [&](ull x){return (mul_mod(x, x, n) + c) % n;};
  98.  
  99.         while(d == 1)
  100.         {
  101.             x = f(x);
  102.             y = f(f(y));
  103.             d = __gcd(x > y ? x - y : y - x, n);
  104.         }
  105.  
  106.         if(d != n) return d;
  107.     }
  108. }
  109.  
  110. map<ull,ll> mp;
  111. void factor(ull n)
  112. {
  113.     if(n == 1) return;
  114.     if(isPrime(n))
  115.     {
  116.         mp[n]++;
  117.         return;
  118.     }
  119.     ull d = pollard(n);
  120.     factor(d);
  121.     factor(n / d);
  122. }
  123.  
  124. vector<pair<ull,ll>> fac;
  125. vector<ull> divi;
  126.  
  127. void gen(int idx,ull cur)
  128. {
  129.         if(idx == sz(fac))
  130.         {
  131.                 divi.pb(cur);
  132.                 return;
  133.         }
  134.  
  135.         ull p = fac[idx].ff,e = fac[idx].ss;
  136.         ull val = 1;
  137.         for(int i = 0 ; i <= e ; i++)
  138.         {
  139.                 gen(idx + 1, cur * val);
  140.                 val *= p;
  141.         }
  142. }
  143.  
  144. void solve()
  145. {
  146.         int t;
  147.         cin >> t;
  148.  
  149.         while(t--)
  150.         {
  151.                 ull n;
  152.                 cin >> n;
  153.  
  154.                 mp.clear();
  155.                 fac.clear();
  156.                 divi.clear();
  157.                 factor(n);
  158.  
  159.                 for(auto x : mp)
  160.                 {
  161.                         fac.pb({x.ff,x.ss});
  162.                 }
  163.  
  164.                 gen(0,1);
  165.  
  166.                 sort(all(divi));
  167.  
  168.                 bool ok = false;
  169.                 for(ull d : divi)
  170.                 {
  171.                         if(d == ULLONG_MAX)  continue;
  172.                         if(d + 1 != 0 && n % (d + 1) == 0)
  173.                         {
  174.                                 cout << d << " ";
  175.                                 ok = true;
  176.                         }
  177.                 }
  178.  
  179.                 if(!ok) cout << -1;
  180.                 cout << en;
  181.  
  182.         }
  183. }
  184.  
  185. int main()
  186. {
  187.         fastIO
  188.  
  189.         solve();
  190.  
  191.         return 0;
  192. }
Success #stdin #stdout 0.01s 5268KB
comments (?)
stdin
copy 
4
35
40
50
60
stdout
copy 
-1
1 4 
1 
1 2 3 4 5
https://ideone.com/Eg37Hh
language:
C++ (gcc 8.3)
created:
3 days 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!