Submit Info #28968

Problem Lang User Status Time Memory
Kth Root(Mod) cpp Jeffrey AC 91 ms 0.74 MiB

ケース詳細
Name Status Time Memory
Tonelli-Shanks_worstcase_00 AC 81 ms 0.52 MiB
Tonelli-Shanks_worstcase_01 AC 91 ms 0.71 MiB
Tonelli-Shanks_worstcase_02 AC 91 ms 0.67 MiB
Tonelli-Shanks_worstcase_03 AC 86 ms 0.74 MiB
Tonelli-Shanks_worstcase_04 AC 79 ms 0.65 MiB
example_00 AC 1 ms 0.67 MiB
max_random_00 AC 29 ms 0.74 MiB
max_random_01 AC 26 ms 0.67 MiB
max_random_02 AC 26 ms 0.67 MiB
max_random_03 AC 26 ms 0.67 MiB
max_random_04 AC 25 ms 0.67 MiB
random_00 AC 4 ms 0.66 MiB
random_01 AC 8 ms 0.62 MiB
random_02 AC 15 ms 0.72 MiB
random_03 AC 3 ms 0.70 MiB
random_04 AC 3 ms 0.62 MiB
safe_prime_00 AC 16 ms 0.68 MiB
safe_prime_01 AC 16 ms 0.67 MiB
safe_prime_02 AC 17 ms 0.67 MiB
safe_prime_03 AC 17 ms 0.67 MiB
safe_prime_04 AC 17 ms 0.67 MiB
small_00 AC 4 ms 0.67 MiB

#include <iostream> #include <algorithm> #include <vector> #include <string> #include <cmath> #include <cassert> #include <map> using namespace std; typedef long long ll; typedef pair<int, int> pii; const int mod = 1000000007; long long pow(long long a, long long n, long long p) { long long r=1; for (;n>0;n>>=1,a=a*a%p)if(n%2==1)r=r*a%p; return r; } int cnt(long long a,long long base,long long p) { int ret=0; while (a!=1) { a=pow(a,base,p); ++ret; } return ret; } long long inv(long long a, long long p) { a%=p; long long u=1, v=0; long long b=p; while (b>0) { long long q=a/b; a%=b; u-=v*q%p; u=(u%p+p)%p; { u^=v;v^=u;u^=v; a^=b;b^=a;a^=b; } } return u<0?u+p:u; } long long gcd(long long a,long long b) { return a==0?b:gcd(b%a,a); } long long peth_root(long long a,long long p,int e,long long mod) { long long q=mod-1; int s=0; while (q%p==0) { q/=p; ++s; } long long pe=pow(p,e,mod); long long ans=pow(a,((pe-1)*inv(q,pe)%pe*q+1)/pe,mod); long long c=2; while (pow(c,(mod-1)/p,mod)==1) ++c; c=pow(c,q,mod); std::map<long long,int> map; long long add=1; int v=(int)std::sqrt((double)(s-e)*p)+1; long long mul=pow(c,v*pow(p,s-1,mod-1)%(mod-1),mod); for (int i=0;i<=v;++i) { map[add]=i; add=add*mul%mod; } mul=inv(pow(c,pow(p,s-1,mod-1),mod),mod); for (int i=e;i<s;++i) { long long err=inv(pow(ans,pe,mod),mod)*a%mod; long long target=pow(err,pow(p,s-1-i,mod-1),mod); for (int j=0; j<=v; ++j) { if (map.find(target)!=map.end()) { int x=map[target]; ans=ans*pow(c,(j+v*x)*pow(p,i-e,mod-1)%(mod-1),mod)%mod; break; } target=target*mul%mod; assert(j!=v); } } return ans; } long long kth_root(long long a,long long k,long long p) { if(k>0&&a==0)return 0; k%=p-1; long long g=gcd(k,p-1); if (pow(a,(p-1)/g,p)!=1) return -1; a=pow(a,inv(k/g,(p-1)/g),p); for (long long div=2;div*div<=g;++div) { int sz=0; while (g%div==0) { g/=div; ++sz; } if (sz>0) { long long b=peth_root(a,div,sz,p); a=b; } } if (g>1) a=peth_root(a,g,1,p); return a; } int main() { ios::sync_with_stdio(false); int t; ll k, y, p; cin >> t; while (t--) { cin >> k >> y >> p; cout << kth_root(y, k, p) << '\n'; } }