Submit Info #24338

Problem Lang User Status Time Memory
Kth Root(Mod) cpp (anonymous) AC 800 ms 1.53 MiB

ケース詳細
Name Status Time Memory
Tonelli-Shanks_worstcase_00 AC 547 ms 0.96 MiB
Tonelli-Shanks_worstcase_01 AC 800 ms 1.04 MiB
Tonelli-Shanks_worstcase_02 AC 715 ms 1.05 MiB
Tonelli-Shanks_worstcase_03 AC 655 ms 1.03 MiB
Tonelli-Shanks_worstcase_04 AC 518 ms 0.95 MiB
example_00 AC 1 ms 0.62 MiB
max_random_00 AC 155 ms 1.00 MiB
max_random_01 AC 163 ms 1.53 MiB
max_random_02 AC 137 ms 0.77 MiB
max_random_03 AC 145 ms 0.80 MiB
max_random_04 AC 153 ms 0.98 MiB
random_00 AC 9 ms 0.61 MiB
random_01 AC 24 ms 0.67 MiB
random_02 AC 38 ms 0.62 MiB
random_03 AC 12 ms 0.67 MiB
random_04 AC 8 ms 0.61 MiB
safe_prime_00 AC 69 ms 0.67 MiB
safe_prime_01 AC 68 ms 0.68 MiB
safe_prime_02 AC 67 ms 0.70 MiB
safe_prime_03 AC 70 ms 0.67 MiB
safe_prime_04 AC 68 ms 0.64 MiB
small_00 AC 5 ms 0.60 MiB

#include<bits/stdc++.h> using namespace std; typedef long long ll; ll qpow(ll a,ll b,ll mod){ ll res=1; assert(b>=0); assert(mod>=0); for(;b;b>>=1){ if(b&1){ res=(__int128)res*a%mod; } a=(__int128)a*a%mod; } return res; } ll mod_inv(ll a, ll m) { // https://en.wikipedia.org/wiki/Extended_Euclidean_algorithm#Example ll g = m, r = a, x = 0, y = 1; while (r != 0) { ll q = g / r; g %= r; swap(g, r); x -= q * y; swap(x, y); } return x < 0 ? x + m : x; } ll BSGS(ll g,ll h,ll order,ll p){ assert(order<=1e14); //g^x=h; static unordered_map<ll,ll>table; table.clear(); int block=sqrt(order)+1; ll s=h; for(int i=0;i<block;i++){ table[s]=i; s=(__int128)s*g%p; } g=qpow(g,block,p);s=1; for(int i=1;i<=block;i++){ s=(__int128)s*g%p; if(table.count(s)){ return 1ll*i*block-table[s]; } } return -1; } mt19937 rd(123); vector<ll> shanks(ll delta,ll r,ll p){ //p and r should be prime if(r==0){ if(delta==1)return {1}; else return {}; } if(delta==0)return {0}; if((p-1)%r){ ll e=mod_inv(r,p-1); assert(e>=0); return {qpow(delta,e,p)}; } if(qpow(delta,(p-1)/r,p)!=1)return {}; //case gcd(r,p-1)=1 only have one solution uniform_int_distribution<>nxt_rnd(1,p-1); ll rho; while(qpow(rho=nxt_rnd(rd),(p-1)/r,p)==1); ll s=(p-1)/r; ll unity=qpow(rho,s,p); int t=1; ll e=1; while(s%r==0)s/=r,t++,e*=r; assert(__gcd(r,s)==1); ll alpha=mod_inv(r,s); ll a=qpow(rho,(p-1)/r,p), b=qpow(delta,r*alpha-1+p-1,p), c=qpow(rho,s,p), h=1; ll phi=p-1; for(int i=1;i<t;i++){ e/=r; ll d=qpow(b,e,p); ll j=(phi-BSGS(a,d,r,p))%phi; ll tmp=qpow(c,j,p); b=(__int128)b*qpow(tmp,r,p)%p; h=(__int128)h*tmp%p; c=qpow(c,r,p); } vector<ll>ans(r); ans[0]=(__int128)qpow(delta,alpha,p)*h%p; for(int i=1;i<r;i++){ ans[i]=(__int128)unity*ans[i-1]%p; } return ans; } vector<ll> shanks(ll delta,vector<ll> r,ll p){ vector<ll>ans[2]; int pos=0; ans[0].push_back(delta); for(auto& i:r){ ans[pos^1].clear(); for(auto& j:ans[pos]){ auto tmp=shanks(j,i,p); ans[pos^1].insert(ans[pos^1].end(),tmp.begin(),tmp.end()); } pos^=1; } return ans[pos]; } const int N=1e5; int p[N/2]; bool vis[N+10]; int main(){ int m=0; int P,A,B; int T; cin>>T; while(T--){ cin>>A>>B>>P; vector<ll>pr; for(int i=2;i*i<=A;i++){ if(A%i==0){ pr.push_back(i); A/=i; while(A%i==0){ pr.push_back(i); A/=i; } } } if(A!=1)pr.push_back(A); auto ans=shanks(B,pr,P); if(ans.empty())puts("-1"); else { cout<<ans.back()<<'\n'; } } }