Ideone.com

fork download

copy

/*
       shool : Cu Chi High School
       participant : Ngo Quoc Binh
*/
#include <bits/stdc++.h>
using namespace std;
 
#define debug(x) cerr << #x << " = " << x << "\n";
#define vdebug(a) cerr << #a << " = "; for(auto x : a) cout << x << " "; cout << "\n";
#define TIME cerr << "\nTime elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s\n";
#define fastIO ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define hashmap unordered_map
#define hashset unordered_set
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define rev(x) reverse(all(x))
#define sz(x) ((int)((x).size()))
#define max_arr(x) *max_element(all(x))
#define min_arr(x) *min_element(all(x))
 
#define pb push_back
#define pf push_front
#define PB pop_back
#define PF pop_front
#define en '\n'
#define ff first
#define ss second
#define task "wtf"
 
using ll = long long;
using ull = unsigned long long;
using ld = long double;
using u128 = __uint128_t;
 
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
 
ull mul_mod(ull a, ull b, ull mod)
{
        return (u128)a * b % mod;
}
 
ull pow_mod(ull a, ull d, ull mod)
{
        ull res = 1;
        while(d)
        {
                if(d & 1) res = mul_mod(res, a, mod);
                a = mul_mod(a, a, mod);
                d >>= 1;
        }
        return res;
}
 
bool isPrime(ull n)
{
        if(n < 2) return false;
        for(ull p : {2,3,5,7,11,13,17,19,23,29,31,37})
        {
                if (n % p == 0) return n == p;
        }
 
        ull d = n - 1, s = 0;
        while((d & 1) == 0)
        {
                d >>= 1;
                s++;
        }
 
        for(ull a : {2ULL,325ULL,9375ULL,28178ULL,450775ULL,9780504ULL,1795265022ULL})
        {
                if (a % n == 0) continue;
                ull x = pow_mod(a, d, n);
                if (x == 1 || x == n - 1) continue;
                bool ok = false;
                for (ull r = 1; r < s; r++) {
                x = mul_mod(x, x, n);
                if (x == n - 1) {
                        ok = true;
                        break;
                }
                }
                if (!ok) return false;
        }
        return true;
}
 
ull pollard(ull n) {
    if (n % 2 == 0) return 2;
 
    while(true)
    {
        ull c = uniform_int_distribution<ull>(1, n - 1)(rng);
        ull x = uniform_int_distribution<ull>(0, n - 1)(rng);
        ull y = x;
        ull d = 1;
 
        auto f = [&](ull x){return (mul_mod(x, x, n) + c) % n;};
 
        while(d == 1)
        {
            x = f(x);
            y = f(f(y));
            d = __gcd(x > y ? x - y : y - x, n);
        }
 
        if(d != n) return d;
    }
}
 
map<ull,ll> mp;
void factor(ull n)
{
    if(n == 1) return;
    if(isPrime(n))
    {
        mp[n]++;
        return;
    }
    ull d = pollard(n);
    factor(d);
    factor(n / d);
}
 
vector<pair<ull,ll>> fac;
vector<ull> divi;
 
void gen(int idx,ull cur)
{
        if(idx == sz(fac))
        {
                divi.pb(cur);
                return;
        }
 
        ull p = fac[idx].ff,e = fac[idx].ss;
        ull val = 1;
        for(int i = 0 ; i <= e ; i++)
        {
                gen(idx + 1, cur * val);
                val *= p;
        }
}
 
void solve()
{
        int t;
        cin >> t;
 
        while(t--)
        {
                ull n;
                cin >> n;
 
                mp.clear();
                fac.clear();
                divi.clear();
                factor(n);
 
                for(auto x : mp)
                {
                        fac.pb({x.ff,x.ss});
                }
 
                gen(0,1);
 
                sort(all(divi));
 
                bool ok = false;
                for(ull d : divi)
                {
                        if(d == ULLONG_MAX)  continue;
                        if(d + 1 != 0 && n % (d + 1) == 0)
                        {
                                cout << d << " ";
                                ok = true;
                        }
                }
 
                if(!ok) cout << -1;
                cout << en;
 
        }
}
 
int main()
{
        fastIO
 
        solve();
 
        return 0;
}

LyoKICAgICAgIHNob29sIDogQ3UgQ2hpIEhpZ2ggU2Nob29sCiAgICAgICBwYXJ0aWNpcGFudCA6IE5nbyBRdW9jIEJpbmgKKi8KI2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CgojZGVmaW5lIGRlYnVnKHgpIGNlcnIgPDwgI3ggPDwgIiA9ICIgPDwgeCA8PCAiXG4iOwojZGVmaW5lIHZkZWJ1ZyhhKSBjZXJyIDw8ICNhIDw8ICIgPSAiOyBmb3IoYXV0byB4IDogYSkgY291dCA8PCB4IDw8ICIgIjsgY291dCA8PCAiXG4iOwojZGVmaW5lIFRJTUUgY2VyciA8PCAiXG5UaW1lIGVsYXBzZWQ6ICIgPDwgMS4wICogY2xvY2soKSAvIENMT0NLU19QRVJfU0VDIDw8ICIgc1xuIjsKI2RlZmluZSBmYXN0SU8gaW9zX2Jhc2U6OnN5bmNfd2l0aF9zdGRpbygwKTtjaW4udGllKDApO2NvdXQudGllKDApOwojZGVmaW5lIGhhc2htYXAgdW5vcmRlcmVkX21hcAojZGVmaW5lIGhhc2hzZXQgdW5vcmRlcmVkX3NldAojZGVmaW5lIGFsbCh4KSAoeCkuYmVnaW4oKSwoeCkuZW5kKCkKI2RlZmluZSByYWxsKHgpICh4KS5yYmVnaW4oKSwoeCkucmVuZCgpCiNkZWZpbmUgcmV2KHgpIHJldmVyc2UoYWxsKHgpKQojZGVmaW5lIHN6KHgpICgoaW50KSgoeCkuc2l6ZSgpKSkKI2RlZmluZSBtYXhfYXJyKHgpICptYXhfZWxlbWVudChhbGwoeCkpCiNkZWZpbmUgbWluX2Fycih4KSAqbWluX2VsZW1lbnQoYWxsKHgpKQoKI2RlZmluZSBwYiBwdXNoX2JhY2sKI2RlZmluZSBwZiBwdXNoX2Zyb250CiNkZWZpbmUgUEIgcG9wX2JhY2sKI2RlZmluZSBQRiBwb3BfZnJvbnQKI2RlZmluZSBlbiAnXG4nCiNkZWZpbmUgZmYgZmlyc3QKI2RlZmluZSBzcyBzZWNvbmQKI2RlZmluZSB0YXNrICJ3dGYiCgp1c2luZyBsbCA9IGxvbmcgbG9uZzsKdXNpbmcgdWxsID0gdW5zaWduZWQgbG9uZyBsb25nOwp1c2luZyBsZCA9IGxvbmcgZG91YmxlOwp1c2luZyB1MTI4ID0gX191aW50MTI4X3Q7CgptdDE5OTM3XzY0IHJuZyhjaHJvbm86OnN0ZWFkeV9jbG9jazo6bm93KCkudGltZV9zaW5jZV9lcG9jaCgpLmNvdW50KCkpOwoKdWxsIG11bF9tb2QodWxsIGEsIHVsbCBiLCB1bGwgbW9kKQp7CiAgICAgICAgcmV0dXJuICh1MTI4KWEgKiBiICUgbW9kOwp9Cgp1bGwgcG93X21vZCh1bGwgYSwgdWxsIGQsIHVsbCBtb2QpCnsKICAgICAgICB1bGwgcmVzID0gMTsKICAgICAgICB3aGlsZShkKQogICAgICAgIHsKICAgICAgICAgICAgICAgIGlmKGQgJiAxKSByZXMgPSBtdWxfbW9kKHJlcywgYSwgbW9kKTsKICAgICAgICAgICAgICAgIGEgPSBtdWxfbW9kKGEsIGEsIG1vZCk7CiAgICAgICAgICAgICAgICBkID4+PSAxOwogICAgICAgIH0KICAgICAgICByZXR1cm4gcmVzOwp9Cgpib29sIGlzUHJpbWUodWxsIG4pCnsKICAgICAgICBpZihuIDwgMikgcmV0dXJuIGZhbHNlOwogICAgICAgIGZvcih1bGwgcCA6IHsyLDMsNSw3LDExLDEzLDE3LDE5LDIzLDI5LDMxLDM3fSkKICAgICAgICB7CiAgICAgICAgICAgICAgICBpZiAobiAlIHAgPT0gMCkgcmV0dXJuIG4gPT0gcDsKICAgICAgICB9CgogICAgICAgIHVsbCBkID0gbiAtIDEsIHMgPSAwOwogICAgICAgIHdoaWxlKChkICYgMSkgPT0gMCkKICAgICAgICB7CiAgICAgICAgICAgICAgICBkID4+PSAxOwogICAgICAgICAgICAgICAgcysrOwogICAgICAgIH0KCiAgICAgICAgZm9yKHVsbCBhIDogezJVTEwsMzI1VUxMLDkzNzVVTEwsMjgxNzhVTEwsNDUwNzc1VUxMLDk3ODA1MDRVTEwsMTc5NTI2NTAyMlVMTH0pCiAgICAgICAgewogICAgICAgICAgICAgICAgaWYgKGEgJSBuID09IDApIGNvbnRpbnVlOwogICAgICAgICAgICAgICAgdWxsIHggPSBwb3dfbW9kKGEsIGQsIG4pOwogICAgICAgICAgICAgICAgaWYgKHggPT0gMSB8fCB4ID09IG4gLSAxKSBjb250aW51ZTsKICAgICAgICAgICAgICAgIGJvb2wgb2sgPSBmYWxzZTsKICAgICAgICAgICAgICAgIGZvciAodWxsIHIgPSAxOyByIDwgczsgcisrKSB7CiAgICAgICAgICAgICAgICB4ID0gbXVsX21vZCh4LCB4LCBuKTsKICAgICAgICAgICAgICAgIGlmICh4ID09IG4gLSAxKSB7CiAgICAgICAgICAgICAgICAgICAgICAgIG9rID0gdHJ1ZTsKICAgICAgICAgICAgICAgICAgICAgICAgYnJlYWs7CiAgICAgICAgICAgICAgICB9CiAgICAgICAgICAgICAgICB9CiAgICAgICAgICAgICAgICBpZiAoIW9rKSByZXR1cm4gZmFsc2U7CiAgICAgICAgfQogICAgICAgIHJldHVybiB0cnVlOwp9Cgp1bGwgcG9sbGFyZCh1bGwgbikgewogICAgaWYgKG4gJSAyID09IDApIHJldHVybiAyOwoKICAgIHdoaWxlKHRydWUpCiAgICB7CiAgICAgICAgdWxsIGMgPSB1bmlmb3JtX2ludF9kaXN0cmlidXRpb248dWxsPigxLCBuIC0gMSkocm5nKTsKICAgICAgICB1bGwgeCA9IHVuaWZvcm1faW50X2Rpc3RyaWJ1dGlvbjx1bGw+KDAsIG4gLSAxKShybmcpOwogICAgICAgIHVsbCB5ID0geDsKICAgICAgICB1bGwgZCA9IDE7CgogICAgICAgIGF1dG8gZiA9IFsmXSh1bGwgeCl7cmV0dXJuIChtdWxfbW9kKHgsIHgsIG4pICsgYykgJSBuO307CgogICAgICAgIHdoaWxlKGQgPT0gMSkKICAgICAgICB7CiAgICAgICAgICAgIHggPSBmKHgpOwogICAgICAgICAgICB5ID0gZihmKHkpKTsKICAgICAgICAgICAgZCA9IF9fZ2NkKHggPiB5ID8geCAtIHkgOiB5IC0geCwgbik7CiAgICAgICAgfQoKICAgICAgICBpZihkICE9IG4pIHJldHVybiBkOwogICAgfQp9CgptYXA8dWxsLGxsPiBtcDsKdm9pZCBmYWN0b3IodWxsIG4pCnsKICAgIGlmKG4gPT0gMSkgcmV0dXJuOwogICAgaWYoaXNQcmltZShuKSkKICAgIHsKICAgICAgICBtcFtuXSsrOwogICAgICAgIHJldHVybjsKICAgIH0KICAgIHVsbCBkID0gcG9sbGFyZChuKTsKICAgIGZhY3RvcihkKTsKICAgIGZhY3RvcihuIC8gZCk7Cn0KCnZlY3RvcjxwYWlyPHVsbCxsbD4+IGZhYzsKdmVjdG9yPHVsbD4gZGl2aTsKCnZvaWQgZ2VuKGludCBpZHgsdWxsIGN1cikKewogICAgICAgIGlmKGlkeCA9PSBzeihmYWMpKQogICAgICAgIHsKICAgICAgICAgICAgICAgIGRpdmkucGIoY3VyKTsKICAgICAgICAgICAgICAgIHJldHVybjsKICAgICAgICB9CgogICAgICAgIHVsbCBwID0gZmFjW2lkeF0uZmYsZSA9IGZhY1tpZHhdLnNzOwogICAgICAgIHVsbCB2YWwgPSAxOwogICAgICAgIGZvcihpbnQgaSA9IDAgOyBpIDw9IGUgOyBpKyspCiAgICAgICAgewogICAgICAgICAgICAgICAgZ2VuKGlkeCArIDEsIGN1ciAqIHZhbCk7CiAgICAgICAgICAgICAgICB2YWwgKj0gcDsKICAgICAgICB9Cn0KCnZvaWQgc29sdmUoKQp7CiAgICAgICAgaW50IHQ7CiAgICAgICAgY2luID4+IHQ7CgogICAgICAgIHdoaWxlKHQtLSkKICAgICAgICB7CiAgICAgICAgICAgICAgICB1bGwgbjsKICAgICAgICAgICAgICAgIGNpbiA+PiBuOwoKICAgICAgICAgICAgICAgIG1wLmNsZWFyKCk7CiAgICAgICAgICAgICAgICBmYWMuY2xlYXIoKTsKICAgICAgICAgICAgICAgIGRpdmkuY2xlYXIoKTsKICAgICAgICAgICAgICAgIGZhY3RvcihuKTsKCiAgICAgICAgICAgICAgICBmb3IoYXV0byB4IDogbXApCiAgICAgICAgICAgICAgICB7CiAgICAgICAgICAgICAgICAgICAgICAgIGZhYy5wYih7eC5mZix4LnNzfSk7CiAgICAgICAgICAgICAgICB9CgogICAgICAgICAgICAgICAgZ2VuKDAsMSk7CgogICAgICAgICAgICAgICAgc29ydChhbGwoZGl2aSkpOwoKICAgICAgICAgICAgICAgIGJvb2wgb2sgPSBmYWxzZTsKICAgICAgICAgICAgICAgIGZvcih1bGwgZCA6IGRpdmkpCiAgICAgICAgICAgICAgICB7CiAgICAgICAgICAgICAgICAgICAgICAgIGlmKGQgPT0gVUxMT05HX01BWCkgIGNvbnRpbnVlOwogICAgICAgICAgICAgICAgICAgICAgICBpZihkICsgMSAhPSAwICYmIG4gJSAoZCArIDEpID09IDApCiAgICAgICAgICAgICAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICBjb3V0IDw8IGQgPDwgIiAiOwogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIG9rID0gdHJ1ZTsKICAgICAgICAgICAgICAgICAgICAgICAgfQogICAgICAgICAgICAgICAgfQoKICAgICAgICAgICAgICAgIGlmKCFvaykgY291dCA8PCAtMTsKICAgICAgICAgICAgICAgIGNvdXQgPDwgZW47CgogICAgICAgIH0KfQoKaW50IG1haW4oKQp7CiAgICAgICAgZmFzdElPCgogICAgICAgIHNvbHZlKCk7CgogICAgICAgIHJldHVybiAwOwp9

Success #stdin #stdout 0.1s 5280KB

stdin

copy

Standard input is empty

stdout

copy

https://ideone.com/Xze8eQ

language:

C++ (gcc 8.3)

created:

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!

Discover > Sphere Engine API

Discover > IDE Widget

Choose your language