QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#354798#6566. Power of Divisorskevinshan#AC ✓0ms3864kbC++177.9kb2024-03-16 01:50:162024-03-16 01:50:16

Judging History

你现在查看的是最新测评结果

  • [2024-03-16 01:50:16]
  • 评测
  • 测评结果:AC
  • 用时:0ms
  • 内存:3864kb
  • [2024-03-16 01:50:16]
  • 提交

answer



#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define all(x) x.begin(), x.end()
#define pb push_back
#define f first
#define s second

#define trav(a,b) for(auto& a:b)
#define sz(a) a.size()

using ul = uint64_t;
using db = double;

#define FOR(i,a,b) for(int i=a;i<b;i++)
#define For(i,a) FOR(i,0,a)

// ul modMul(ul a, ul b, const ul mod) {
// 	ll ret = a*b-mod*(ul)((db)a*b/mod);
// 	return ret+((ret<0)-(ret>=(ll)mod))*mod; }
// ul modPow(ul a, ul b, const ul mod) {
// 	if (b == 0) return 1;
// 	ul res = modPow(a,b/2,mod); res = modMul(res,res,mod);
// 	return b&1 ? modMul(res,a,mod) : res;
// }

// bool prime(ul n) { // not ll!
// 	if (n < 2 || n % 6 % 4 != 1) return n-2 < 2;
// 	ul A[] = {2, 325, 9375, 28178, 450775, 9780504, 1795265022},
// 	    s = __builtin_ctzll(n-1), d = n>>s;
// 	trav(a,A) {   // ^ count trailing zeroes
// 		ul p = modPow(a,d,n), i = s;
// 		while (p != 1 && p != n-1 && a%n && i--) p = modMul(p,p,n);
// 		if (p != n-1 && i != s) return 0;
// 	}
// 	return 1;
// }

uint64_t mod_pow( uint64_t x, uint64_t y, uint64_t mod ) {
    uint64_t ret = 1;
    uint64_t acc = x;
    for( ; y; y >>= 1 ) {
        if( y & 1 ) {
            ret = __uint128_t(ret) * acc % mod;
        }
        acc = __uint128_t(acc) * acc % mod;
    }
    return ret;
}


bool miller_rabin( uint64_t n, const std::initializer_list<uint64_t>& as ) {
    return std::all_of( as.begin(), as.end(), [n]( uint64_t a ) {
        if( n <= a ) { return true; }

        int e = __builtin_ctzll( n - 1 );
        uint64_t z = mod_pow( a, ( n - 1 ) >> e, n );
        if( z == 1 || z == n - 1 ) { return true; }

        while( --e ) {
            z = __uint128_t(z) * z % n;
            if( z == 1 ) { return false; }
            if( z == n - 1 ) { return true; }
        }

        return false;
    });
}

bool is_prime( uint64_t n ) {
    if( n == 2 ) { return true; }
    if( n % 2 == 0 ) { return false; }
    if( n < 4759123141 ) { return miller_rabin( n, { 2, 7, 61 } ); }
    return miller_rabin( n, { 2, 325, 9375, 28178, 450775, 9780504, 1795265022 } );
}

class Montgomery {
    uint64_t mod;
    uint64_t R;
public:
    Montgomery( uint64_t n ) : mod(n), R(n) {
       for( size_t i = 0; i < 5; ++i ) {
          R *= 2 - mod * R;
       }
    }

    uint64_t fma( uint64_t a, uint64_t b, uint64_t c ) const {
        const __uint128_t d = __uint128_t(a) * b;
        const uint64_t    e = c + mod + ( d >> 64 );
        const uint64_t    f = uint64_t(d) * R;
        const uint64_t    g = ( __uint128_t(f) * mod ) >> 64;
        return e - g;
    }

    uint64_t mul( uint64_t a, uint64_t b ) const {
        return fma( a, b, 0 );
    }
};

// ul pollard(ul n) { // return some nontrivial factor of n
// 	auto f = [n](ul x) { return modMul(x, x, n) + 1; };
// 	ul x = 0, y = 0, t = 30, prd = 2, i = 1, q;
// 	while (t++ % 40 || gcd(prd, n) == 1) { /// speedup: don't take gcd every it
// 		if (x == y) x = ++i, y = f(x);
// 		if ((q = modMul(prd, max(x,y)-min(x,y), n))) prd = q;
// 		x = f(x), y = f(f(y));
// 	}
// 	return gcd(prd, n);
// }
// void factor_rec(ul n, map<ul,int>& cnt) {
// 	if (n == 1) return;
// 	if (prime(n)) { ++cnt[n]; return; }
// 	ul u = pollard(n);
// 	factor_rec(u,cnt), factor_rec(n/u,cnt);
// }

// vector<pair<ul,int>> factor(ul n) {
//  	map<ul,int> cnt; factor_rec(n,cnt);
//  	return vector<pair<ul,int>>(all(cnt));
// }

uint64_t gcd_stein_impl( uint64_t x, uint64_t y ) {
    if( x == y ) { return x; }
    const uint64_t a = y - x;
    const uint64_t b = x - y;
    const int n = __builtin_ctzll( b );
    const uint64_t s = x < y ? a : b;
    const uint64_t t = x < y ? x : y;
    return gcd_stein_impl( s >> n, t );
}

uint64_t gcd_stein( uint64_t x, uint64_t y ) {
    if( x == 0 ) { return y; }
    if( y == 0 ) { return x; }
    const int n = __builtin_ctzll( x );
    const int m = __builtin_ctzll( y );
    return gcd_stein_impl( x >> n, y >> m ) << ( n < m ? n : m );
}


uint64_t pollard_rho( uint64_t n ) {
    if( n % 2 == 0 ) { return 2; }
    const Montgomery m( n );

    constexpr uint64_t C1 = 1;
    constexpr uint64_t C2 = 2;
    constexpr uint64_t M = 512;

    uint64_t Z1 = 1;
    uint64_t Z2 = 2;
retry:
    uint64_t z1 = Z1;
    uint64_t z2 = Z2;
    for( size_t k = M; ; k *= 2 ) {
        const uint64_t x1 = z1 + n;
        const uint64_t x2 = z2 + n;
        for( size_t j = 0; j < k; j += M ) {
            const uint64_t y1 = z1;
            const uint64_t y2 = z2;

            uint64_t q1 = 1;
            uint64_t q2 = 2;
            z1 = m.fma( z1, z1, C1 );
            z2 = m.fma( z2, z2, C2 );
            for( size_t i = 0; i < M; ++i ) {
                const uint64_t t1 = x1 - z1;
                const uint64_t t2 = x2 - z2;
                z1 = m.fma( z1, z1, C1 );
                z2 = m.fma( z2, z2, C2 );
                q1 = m.mul( q1, t1 );
                q2 = m.mul( q2, t2 );
            }
            q1 = m.mul( q1, x1 - z1 );
            q2 = m.mul( q2, x2 - z2 );

            const uint64_t q3 = m.mul( q1, q2 );
            const uint64_t g3 = gcd_stein( n, q3 );
            if( g3 == 1 ) { continue; }
            if( g3 != n ) { return g3; }

            const uint64_t g1 = gcd_stein( n, q1 );
            const uint64_t g2 = gcd_stein( n, q2 );

            const uint64_t C = g1 != 1 ? C1 : C2;
            const uint64_t x = g1 != 1 ? x1 : x2;
            uint64_t       z = g1 != 1 ? y1 : y2;
            uint64_t       g = g1 != 1 ? g1 : g2;

            if( g == n ) {
                do {
                    z = m.fma( z, z, C );
                    g = gcd_stein( n, x - z );
                } while( g == 1 );
            }
            if( g != n ) {
                return g;
            }

            Z1 += 2;
            Z2 += 2;
            goto retry;
        }
    }
}

void factorize_impl( uint64_t n, std::vector<uint64_t>& ret ) {
    if( n <= 1 ) { return; }
    if( is_prime( n ) ) { ret.push_back( n ); return; }

    const uint64_t p = pollard_rho( n );

    factorize_impl( p, ret );
    factorize_impl( n / p, ret );
}

std::vector<uint64_t> factorize( uint64_t n ) {
    std::vector<uint64_t> ret;
    factorize_impl( n, ret );
    std::sort( ret.begin(), ret.end() );
    return ret;
}

const ll INF = 1e18;

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    if (fopen("input.in", "r")) {
        freopen("input.in", "r", stdin);
        freopen("output.out", "w", stdout);
    }
    ul x; cin>>x;
    auto tmp = factorize(x);
    map<ll,int> y;
    trav(a, tmp) {
        y[a]++;
        // cout << a << endl;
    }
    // vector<pair<ul,int>> y = factor(x);
    // trav(a,y) {
    //     cout << a.f << ' ' << a.s << endl;
    // }
    if(!y.size()) {
        cout << 1 << endl;
        return 0;
    }
    assert(y.size());
    int cur = y.begin()->s;
    trav(a,y) {
        cur = gcd(cur, a.s);
    }

    // cout << "CUR " << cur << endl;

    // vector<int> tmp = getDivi(cur);

    for(int a=1; a<=cur; a++) {
        ll base = 1;
        ll pw2 = 1;
        // cout << "A " << a << endl;
        trav(b, y) {
            int pw = b.s/cur*a;
            for(int i=0;i<pw;i++) {
                if (base > INF/b.f) {
                    cout << -1 << endl;
                    return 0;
                }
                base *= b.f;
            }
            pw2 *= (1+pw);
        }

        ll ans = 1;
        // assert(base != 1);
        for (int i=0;i<pw2;i++) {
            if (ans > INF/base) {
                cout << -1 << endl;
                return 0;
            }
            ans *= base;
            if(i > 100) {
                cout << -1 << endl;
                return 0;
            }
        }
        if (ans==x) {
            cout << base << endl;
            return 0;
        }
    }
    cout << -1 << endl;
    return 0;
}


详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 3636kb

input:

15625

output:

25

result:

ok single line: '25'

Test #2:

score: 0
Accepted
time: 0ms
memory: 3512kb

input:

64000000

output:

20

result:

ok single line: '20'

Test #3:

score: 0
Accepted
time: 0ms
memory: 3560kb

input:

65536

output:

-1

result:

ok single line: '-1'

Test #4:

score: 0
Accepted
time: 0ms
memory: 3568kb

input:

1

output:

1

result:

ok single line: '1'

Test #5:

score: 0
Accepted
time: 0ms
memory: 3516kb

input:

10

output:

-1

result:

ok single line: '-1'

Test #6:

score: 0
Accepted
time: 0ms
memory: 3560kb

input:

100

output:

-1

result:

ok single line: '-1'

Test #7:

score: 0
Accepted
time: 0ms
memory: 3604kb

input:

10000

output:

10

result:

ok single line: '10'

Test #8:

score: 0
Accepted
time: 0ms
memory: 3628kb

input:

1000000000000000000

output:

100

result:

ok single line: '100'

Test #9:

score: 0
Accepted
time: 0ms
memory: 3568kb

input:

10372926089038969

output:

218089

result:

ok single line: '218089'

Test #10:

score: 0
Accepted
time: 0ms
memory: 3572kb

input:

10642944803293201

output:

10157

result:

ok single line: '10157'

Test #11:

score: 0
Accepted
time: 0ms
memory: 3576kb

input:

10646534823110209

output:

103182047

result:

ok single line: '103182047'

Test #12:

score: 0
Accepted
time: 0ms
memory: 3568kb

input:

1073741824

output:

32

result:

ok single line: '32'

Test #13:

score: 0
Accepted
time: 0ms
memory: 3632kb

input:

121

output:

11

result:

ok single line: '11'

Test #14:

score: 0
Accepted
time: 0ms
memory: 3600kb

input:

1296

output:

6

result:

ok single line: '6'

Test #15:

score: 0
Accepted
time: 0ms
memory: 3864kb

input:

16

output:

-1

result:

ok single line: '-1'

Test #16:

score: 0
Accepted
time: 0ms
memory: 3856kb

input:

16277421889

output:

127583

result:

ok single line: '127583'

Test #17:

score: 0
Accepted
time: 0ms
memory: 3628kb

input:

169

output:

13

result:

ok single line: '13'

Test #18:

score: 0
Accepted
time: 0ms
memory: 3564kb

input:

1985984

output:

-1

result:

ok single line: '-1'

Test #19:

score: 0
Accepted
time: 0ms
memory: 3572kb

input:

2

output:

-1

result:

ok single line: '-1'

Test #20:

score: 0
Accepted
time: 0ms
memory: 3624kb

input:

205891132094649

output:

243

result:

ok single line: '243'

Test #21:

score: 0
Accepted
time: 0ms
memory: 3628kb

input:

25

output:

5

result:

ok single line: '5'

Test #22:

score: 0
Accepted
time: 0ms
memory: 3560kb

input:

2626114239841

output:

1273

result:

ok single line: '1273'

Test #23:

score: 0
Accepted
time: 0ms
memory: 3568kb

input:

26269395104446321

output:

12731

result:

ok single line: '12731'

Test #24:

score: 0
Accepted
time: 0ms
memory: 3824kb

input:

3

output:

-1

result:

ok single line: '-1'

Test #25:

score: 0
Accepted
time: 0ms
memory: 3632kb

input:

3596345248055296

output:

88

result:

ok single line: '88'

Test #26:

score: 0
Accepted
time: 0ms
memory: 3624kb

input:

36

output:

-1

result:

ok single line: '-1'

Test #27:

score: 0
Accepted
time: 0ms
memory: 3864kb

input:

4

output:

2

result:

ok single line: '2'

Test #28:

score: 0
Accepted
time: 0ms
memory: 3568kb

input:

4096

output:

8

result:

ok single line: '8'

Test #29:

score: 0
Accepted
time: 0ms
memory: 3568kb

input:

49

output:

7

result:

ok single line: '7'

Test #30:

score: 0
Accepted
time: 0ms
memory: 3856kb

input:

5

output:

-1

result:

ok single line: '-1'

Test #31:

score: 0
Accepted
time: 0ms
memory: 3864kb

input:

576460752303423488

output:

-1

result:

ok single line: '-1'

Test #32:

score: 0
Accepted
time: 0ms
memory: 3792kb

input:

581431415926321

output:

24112889

result:

ok single line: '24112889'

Test #33:

score: 0
Accepted
time: 0ms
memory: 3636kb

input:

6

output:

-1

result:

ok single line: '-1'

Test #34:

score: 0
Accepted
time: 0ms
memory: 3564kb

input:

64

output:

4

result:

ok single line: '4'

Test #35:

score: 0
Accepted
time: 0ms
memory: 3860kb

input:

656100000000

output:

30

result:

ok single line: '30'

Test #36:

score: 0
Accepted
time: 0ms
memory: 3636kb

input:

7

output:

-1

result:

ok single line: '-1'

Test #37:

score: 0
Accepted
time: 0ms
memory: 3632kb

input:

729

output:

9

result:

ok single line: '9'

Test #38:

score: 0
Accepted
time: 0ms
memory: 3668kb

input:

8

output:

-1

result:

ok single line: '-1'

Test #39:

score: 0
Accepted
time: 0ms
memory: 3532kb

input:

81

output:

-1

result:

ok single line: '-1'

Test #40:

score: 0
Accepted
time: 0ms
memory: 3632kb

input:

8527674378686464

output:

452

result:

ok single line: '452'

Test #41:

score: 0
Accepted
time: 0ms
memory: 3856kb

input:

9

output:

3

result:

ok single line: '3'

Test #42:

score: 0
Accepted
time: 0ms
memory: 3532kb

input:

982134461213542729

output:

994009

result:

ok single line: '994009'

Test #43:

score: 0
Accepted
time: 0ms
memory: 3604kb

input:

9992002399680016

output:

9998

result:

ok single line: '9998'

Test #44:

score: 0
Accepted
time: 0ms
memory: 3564kb

input:

999269311525198921

output:

-1

result:

ok single line: '-1'

Test #45:

score: 0
Accepted
time: 0ms
memory: 3860kb

input:

999949000866995087

output:

-1

result:

ok single line: '-1'

Test #46:

score: 0
Accepted
time: 0ms
memory: 3632kb

input:

999995482005103081

output:

-1

result:

ok single line: '-1'

Test #47:

score: 0
Accepted
time: 0ms
memory: 3864kb

input:

999999969999997921

output:

-1

result:

ok single line: '-1'

Test #48:

score: 0
Accepted
time: 0ms
memory: 3788kb

input:

999999999999999989

output:

-1

result:

ok single line: '-1'

Test #49:

score: 0
Accepted
time: 0ms
memory: 3568kb

input:

999999999999999999

output:

-1

result:

ok single line: '-1'