QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#354798 | #6566. Power of Divisors | kevinshan# | AC ✓ | 0ms | 3864kb | C++17 | 7.9kb | 2024-03-16 01:50:16 | 2024-03-16 01:50:16 |
Judging History
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;
}
Details
Tip: Click on the bar to expand more detailed information
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'