結果
問題 | No.981 一般冪乗根 |
ユーザー |
👑 ![]() |
提出日時 | 2020-02-10 15:19:52 |
言語 | C (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 10 ms / 6,000 ms |
コード長 | 1,929 bytes |
コンパイル時間 | 531 ms |
コンパイル使用メモリ | 32,368 KB |
実行使用メモリ | 8,480 KB |
最終ジャッジ日時 | 2024-10-09 21:46:11 |
合計ジャッジ時間 | 83,490 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 30 WA * 8 TLE * 6 |
ソースコード
#include<stdio.h>#include<time.h>#define ll long longll powmod(ll a,ll n,int m){ll x=1;a%=m;while(n){if(n%2)x=x*a%m;a=a*a%m;n/=2;}return x;}ll gcd(ll x,ll y){while(y){ll t=x%y;x=y;y=t;}return x;}ll inv(ll a,ll p){ll b=p,tx,ty,t,x=1,y=0,x2=0,y2=1;while(b){tx=x-a/b*x2;x=x2;x2=tx;ty=y-a/b*y2;y=y2;y2=ty;t=a%b;a=b;b=t;}if(a!=1)return-1;return x>0?x:x+p;}int subsub(ll x,ll y,int p,int mod){//(Z/modZ)^*における位数pの元x,yに対し、x^n*y=1を満たすnを返すint cnt=0;while(y!=1){y=y*x%mod;cnt++;}return cnt;}int modrootsub(int a,int p,int e,int mod){int q=mod-1;int s=0;while(q%p==0)q/=p,s++;// Z/(p^s)Z * Z/qZint pe=1;for(int i=0;i<e;i++)pe*=p;// int d=crt(pe-1,pe,0,q);ll d=inv(pe-q%pe,pe)*q;// (p^e)ans = a + errll ans=powmod(a,(d+1)/pe,mod);ll err=powmod(a, d ,mod);if(err==1)return ans;int temp=1;while(powmod(++temp,(mod-1)/p,mod)==1);int z=powmod(temp,q,mod);int g=powmod(temp,(mod-1)/p,mod);while(err!=1){//上から非0の桁数を求めるint t=err,pre,cnt=0;while(t!=1){pre=t;t=powmod(t,p,mod);cnt++;}int n=subsub(g,pre,p,mod);//所定の桁を良しなにする//ansにz^(p^(s-cnt-e)*n)//errにz^(p^(s-cnt )*n)t=powmod(z,n,mod);for(int i=0;i<s-cnt-e;i++)t=powmod(t,p,mod);ans=ans*t%mod;for(int i=0;i<e;i++)t=powmod(t,p,mod);err=err*t%mod;}return ans;}int modroot(int a,int n,int p){//p は素数//x^n=a mod pとなるxの1つを返すint d=gcd(p-1,n);if(powmod(a,(p-1)/d,p)!=1)return -1;a=powmod(a,inv(n/d,(p-1)/d),p);n=d;for(int i=2;i*i<=n;i++)if(n%i==0){n/=i;int e=1;while(n%i==0)n/=i,e++;a=modrootsub(a,i,e,p);}if(n>1)a=modrootsub(a,n,1,p);return a;}int main(){int t;scanf("%d",&t);while(t--){int a,n,m;scanf("%d%d%d",&m,&n,&a);printf("%d\n",modroot(a,n,m));}}