Submit Info #6863

Problem Lang User Status Time Memory
Kth Root(Mod) cpp kyoprofriends AC 406 ms 0.72 MiB

ケース詳細
Name Status Time Memory
Tonelli-Shanks_worstcase_00 AC 298 ms 0.67 MiB
Tonelli-Shanks_worstcase_01 AC 406 ms 0.72 MiB
Tonelli-Shanks_worstcase_02 AC 401 ms 0.72 MiB
Tonelli-Shanks_worstcase_03 AC 363 ms 0.68 MiB
Tonelli-Shanks_worstcase_04 AC 283 ms 0.68 MiB
example_00 AC 2 ms 0.72 MiB
max_random_00 AC 25 ms 0.68 MiB
max_random_01 AC 25 ms 0.67 MiB
max_random_02 AC 20 ms 0.61 MiB
max_random_03 AC 25 ms 0.72 MiB
max_random_04 AC 22 ms 0.67 MiB
random_00 AC 3 ms 0.71 MiB
random_01 AC 12 ms 0.67 MiB
random_02 AC 11 ms 0.67 MiB
random_03 AC 5 ms 0.67 MiB
random_04 AC 2 ms 0.67 MiB
safe_prime_00 AC 12 ms 0.68 MiB
safe_prime_01 AC 18 ms 0.67 MiB
safe_prime_02 AC 12 ms 0.72 MiB
safe_prime_03 AC 17 ms 0.61 MiB
safe_prime_04 AC 16 ms 0.67 MiB
small_00 AC 4 ms 0.67 MiB

#include<stdio.h> #include<math.h> #define ll long long ll pom(ll a,ll n,int m){ll x=1;for(a%=m;n;n/=2)n&1?x=x*a%m:0,a=a*a%m;return x;} ll gcd(ll p,ll q){for(ll t;q;)t=p%q,p=q,q=t;return p;} ll exgcd(ll p,ll q,ll*x,ll*y){ ll tx,ty,t,x2=0,y2=1; *x=1;*y=0; while(q){ tx=*x-p/q*x2;*x=x2;x2=tx; ty=*y-p/q*y2;*y=y2;y2=ty; t=p%q;p=q;q=t; } return p; } ll inv(ll a,ll p){ ll x,y; ll d=exgcd(a,p,&x,&y); if(d!=1)return-1; return x>0?x:x+p; } ll sq(ll n){ll x=sqrt(n);for(;(x+1)*(x+1)<=n;x++);return x;} ll cb(ll n){ll x=cbrt(n);for(;(x+1)*(x+1)*(x+1)<=n;x++);return x;} int subsub(ll x,ll y,int p,int mod){ int cnt=0; for(;y!=1;y=y*x%mod)cnt++; return cnt; } ll modrootsub(ll a,ll p,ll e,ll mod){ ll q=mod-1; int s=0; while(q%p==0)q/=p,s++; ll pe=1; for(int i=0;i<e;i++)pe*=p; ll d=inv(pe-q%pe,pe)*q; ll ans=pom(a,(d+1)/pe,mod); ll err=pom(a, d ,mod); if(err==1)return ans; int temp=1; while(pom(++temp,(mod-1)/p,mod)==1); int z=pom(temp,q,mod); int g=pom(temp,(mod-1)/p,mod); while(err!=1){ int t=err,pre,cnt=0; while(t!=1){ pre=t; t=pom(t,p,mod); cnt++; } int n=subsub(g,pre,p,mod); t=pom(z,n,mod); for(int i=0;i<s-cnt-e;i++)t=pom(t,p,mod); ans=ans*t%mod; for(int i=0;i<e;i++)t=pom(t,p,mod); err=err*t%mod; } return ans; } ll modrootsub2(ll a,ll n,ll p){ ll p1=p-1,p2=1; for(ll temp;temp=gcd(p1,n),temp!=1;)p1/=temp,p2*=temp; ll d=inv(n%p1,p1); return pom(a,d,p); } ll modroot(ll a,ll n,ll p){ if(a==0)return n?0:-1; ll d=gcd(p-1,n); if(pom(a,(p-1)/d,p)!=1)return -1; a=pom(a,inv(n/d,(p-1)/d),p); n=d; ll d1=n,d2=1; for(ll temp;temp=gcd((p-1)/n,d1),temp!=1;)d1/=temp,d2*=temp; a=modrootsub2(a,d1,p); for(ll i=2;i*i*i*i<=p-1;i++)if(d2%i==0){ d2/=i; int e=1; while(d2%i==0)d2/=i,e++; a=modrootsub(a,i,e,p); } if(d2!=1){ ll q2=sq(d2); ll q3=cb(d2); if(q2*q2==d2)a=modrootsub(a,q2,2,p); else if(q3*q3*q3==d2)a=modrootsub(a,q3,3,p); else a=modrootsub(a,d2,1,p); } return a; } int main(){ int t; scanf("%d",&t); while(t--){ ll a,n,m; scanf("%lld%lld%lld",&n,&a,&m); printf("%lld\n",modroot(a,n,m)); } }