Submit Info #18396

Problem Lang User Status Time Memory
Kth Root(Mod) cpp harrybehemoth AC 65 ms 0.75 MiB

ケース詳細
Name Status Time Memory
Tonelli-Shanks_worstcase_00 AC 58 ms 0.68 MiB
Tonelli-Shanks_worstcase_01 AC 64 ms 0.67 MiB
Tonelli-Shanks_worstcase_02 AC 65 ms 0.67 MiB
Tonelli-Shanks_worstcase_03 AC 63 ms 0.67 MiB
Tonelli-Shanks_worstcase_04 AC 56 ms 0.67 MiB
example_00 AC 2 ms 0.67 MiB
max_random_00 AC 19 ms 0.67 MiB
max_random_01 AC 18 ms 0.67 MiB
max_random_02 AC 19 ms 0.67 MiB
max_random_03 AC 19 ms 0.75 MiB
max_random_04 AC 19 ms 0.67 MiB
random_00 AC 5 ms 0.67 MiB
random_01 AC 5 ms 0.67 MiB
random_02 AC 8 ms 0.61 MiB
random_03 AC 2 ms 0.37 MiB
random_04 AC 3 ms 0.67 MiB
safe_prime_00 AC 16 ms 0.72 MiB
safe_prime_01 AC 11 ms 0.67 MiB
safe_prime_02 AC 10 ms 0.67 MiB
safe_prime_03 AC 10 ms 0.65 MiB
safe_prime_04 AC 12 ms 0.67 MiB
small_00 AC 3 ms 0.67 MiB

// Kth ROOT MOD // https://judge.yosupo.jp/problem/kth_root_mod #include <iostream> #include <vector> #include <algorithm> #include <cmath> #include <unordered_map> using namespace std; typedef int64_t LI; LI modPow( LI p, LI e, LI M ) { LI ret = 1; for( ; e>0 ; e>>=1 ) { if( e & 1 ) ret = ret*p %M; p = p*p %M; } return ret; } // FINDS X, Y gcd WHERE aX + bY = gcd( a, b ) LI extendedEuclid( LI a, LI b, LI& X, LI& Y ) { LI x = 1, y = 0, xLast = 0, yLast = 1; LI q, r, m, n; while( a != 0 ) { q = b/a; r = b % a; m = xLast - q*x; n = yLast - q*y; xLast = x; yLast = y; x = m; y = n; b = a; a = r; } X = xLast; Y = yLast; return b; } LI modInv( LI a, LI m ) { LI x, y; LI val = extendedEuclid( a, m, x, y ); if( x < 0 ) return x + m; return x; } LI generator( LI p ) { vector<LI> fact; int phi = p-1, n = phi; for( LI i=2 ; i*i<=n ; ++i ) if( n %i == 0 ) { fact.push_back ( i ); while( n %i == 0 ) n /= i; } if( n > 1 ) fact.push_back( n ); for( LI res=2 ; res<=p ; ++res ) { bool ok = true; for( size_t i=0 ; i<fact.size() && ok ; ++i ) ok &= modPow( res, phi/fact[i], p ) != 1; if( ok ) return res; } return -1; } LI PthRoot( LI a, LI p, int e, LI m ) { unordered_map<LI, int> mp; LI q = m - 1; int s = 0; while( q %p == 0 ) { q /= p; ++s; } LI pe = modPow( p, e, m ); LI ans = modPow( a, ( ( pe - 1 ) * modInv( q, pe ) %pe *q + 1 )/pe, m ); LI c = 2; while( modPow( c, ( m - 1 )/p, m ) == 1 ) ++c; c = modPow( c, q, m ); LI add = 1; int v = sqrt( p ) + 1; LI mul = modPow( c, v*modPow( p, s - 1, m - 1 ), m ); for( int i=0 ; i<=v ; ++i ) { mp[add] = i; add = add*mul %m; } mul = modInv( modPow( c, modPow( p, s - 1, m - 1 ), m ), m ); for( int i=e ; i<s ; ++i ) { LI err = modInv( modPow( ans, pe, m ), m )*a %m; LI target = modPow( err, modPow( p, s - 1 - i, m - 1 ), m ); for( int j=0 ; j<=v ; ++j ) { auto iter = mp.find( target %m ); if( iter != mp.end() ) { int x = iter->second; ans = ans * modPow( c, ( j + v*x ) * modPow( p, i - e, m - 1 ) %( m - 1 ), m ) %m; break; } target = target*mul %m; } } return ans; } LI KthRoot( LI k, LI a, LI p ) { if( k == 0 ) return a == 1 ? 1 : -1; if( k > 0 && a == 0 ) return 0; LI X, Y; LI g = extendedEuclid( k, p - 1, X, Y ); if( g == 1 ) { if( X < 0 ) return modInv( modPow( a, -X, p ), p ); else return modPow( a, X, p ); } if( modPow( a, ( p - 1 )/g, p ) != 1 ) return -1; a = modPow( a, modInv( k/g, ( p - 1 )/g ), p ); for( LI dvsr=2 ; dvsr*dvsr<=g ; ++dvsr ) { int sz = 0; while( g %dvsr == 0 ) { g /= dvsr; ++sz; } if( sz > 0 ) { LI b = PthRoot( a, dvsr, sz, p ); a = b; } } if( g > 1 ) a = PthRoot( a, g, 1, p ); return a; } int main() { ios::sync_with_stdio( 0 ); cin.tie( 0 ); int T; cin >> T; while( T-- ) { LI K, Y, P; cin >> K >> Y >> P; cout << KthRoot( K, Y, P ) << '\n'; } return 0; }