結果
問題 | No.981 一般冪乗根 |
ユーザー | ace_amuro |
提出日時 | 2021-01-22 17:33:45 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
TLE
|
実行時間 | - |
コード長 | 3,214 bytes |
コンパイル時間 | 839 ms |
コンパイル使用メモリ | 83,916 KB |
実行使用メモリ | 24,320 KB |
最終ジャッジ日時 | 2024-06-08 05:40:59 |
合計ジャッジ時間 | 17,859 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | TLE | - |
testcase_01 | -- | - |
testcase_02 | -- | - |
testcase_03 | -- | - |
testcase_04 | -- | - |
testcase_05 | -- | - |
testcase_06 | -- | - |
testcase_07 | -- | - |
testcase_08 | -- | - |
testcase_09 | -- | - |
testcase_10 | -- | - |
testcase_11 | -- | - |
testcase_12 | -- | - |
testcase_13 | -- | - |
testcase_14 | -- | - |
testcase_15 | -- | - |
testcase_16 | -- | - |
testcase_17 | -- | - |
testcase_18 | -- | - |
testcase_19 | -- | - |
testcase_20 | -- | - |
testcase_21 | -- | - |
testcase_22 | -- | - |
testcase_23 | -- | - |
testcase_24 | -- | - |
testcase_25 | -- | - |
testcase_26 | -- | - |
testcase_27 | -- | - |
testcase_28 | -- | - |
evil_60bit1.txt | -- | - |
evil_60bit2.txt | -- | - |
evil_60bit3.txt | -- | - |
evil_hack | -- | - |
evil_hard_random | -- | - |
evil_hard_safeprime.txt | -- | - |
evil_hard_tonelli0 | -- | - |
evil_hard_tonelli1 | -- | - |
evil_hard_tonelli2 | -- | - |
evil_hard_tonelli3 | -- | - |
evil_sefeprime1.txt | -- | - |
evil_sefeprime2.txt | -- | - |
evil_sefeprime3.txt | -- | - |
evil_tonelli1.txt | -- | - |
evil_tonelli2.txt | -- | - |
ソースコード
#include<cstdio> #include<cstring> #include<iostream> #include<cmath> #include<string> #include<algorithm> #include<vector> #include<queue> #include<map> using namespace std; typedef long long LL; const int M=1e7+10; LL qmul(LL a,LL b,LL mod){ LL ans=0; if(b<0){a=-a;b=-b;} while(b>0) { if(b&1) ans=(ans+a)%mod; a=(a+a)%mod; b>>=1; } return ans; } LL qpow(LL a, LL b, LL mod){ if(b==0)return 1ll; LL ans=1; while(b>0){ if(b&1)ans=qmul(ans,a,mod); a=qmul(a,a,mod); b>>=1; } return ans; } LL gcd(LL a,LL b){ while(b){ LL t=a%b; a=b; b=t; } return b; } LL exgcd(LL a,LL b,LL &x,LL &y){ if(b == 0){ x = 1, y = 0; return a; } LL d = exgcd(b, a%b, x, y); LL t = y; y = x - y * (a / b); x = t; return d; } LL solveLinear(LL a,LL b,LL p){//ax=b mod p a=(a%p+p)%p;b=(b%p+p)%p; LL x,y; LL d=exgcd(a,p,x,y); //printf("d=%lld x=%lld y=%lld\n",d,x,y); if(b%d!=0) return -1; return (qmul(b/d,x,p/d)+p/d)%(p/d); } LL invP(LL a,LL p){ a=(a%p+p)%p; if(a==0) return -1; LL x,y; exgcd(a,p,x,y); return (x%p+p)%p; } LL primeroot(LL P){ LL temp[1000],cnt; LL x=P-1; cnt=0; for(LL i=2;i*i<=x;i++){ if(x%i==0){ while(x%i==0){ x/=i; } temp[cnt]=i; cnt++; } } if(x>1){ temp[cnt]=x; cnt++; } for(LL g=2;g<=P-1;g++){ bool flag=1; for(int i=0;i<cnt;i++){ if(qpow(g,(P-1)/temp[i],P)==1){ flag=false; break; } } if(flag){ return g; } } return -1; } const LL hashmod=999983; LL phash[hashmod+100]; LL r_origin[hashmod+100]; LL bsgs(LL a, LL b, LL p){//计算使得a^k=b modp的最小k if(a % p == 0 && b % p == 0) return 1; if(a % p == 0 && b % p != 0) return -1; if(b % p == 1) return 0; LL m = (LL)ceil(sqrt(p)); a = (a%p+p)%p; LL r = (b%p+p)%p; memset(phash,-1,sizeof(phash)); memset(r_origin,-1,sizeof(r_origin)); LL k; phash[r%hashmod] = 0;//建立hash r_origin[r%hashmod]=r; for(LL j = 1; j < m; j++){//baby step r = qmul(r, a, p); k=r%hashmod; while(phash[k]!=-1) k++; phash[k] = j; r_origin[k]=r; } LL am = qpow(a, m ,p);//快速幂计算a^m LL t = 1; for(LL i = 1; i <= m; i++){//giant step t = qmul(t, am, p); k=t%hashmod; if(phash[k]!=-1){ while(phash[k]!=-1){ if(r_origin[k]==t) return m * i - phash[k]; k++; } } } return -1; } LL work(LL P,LL n,LL A){ LL g=primeroot(P); //printf("g=%lld\n",g); LL a=bsgs(g,A,P); //printf("a=%lld\n",a); LL x=solveLinear(n,a,P-1); //printf("x=%lld\n",x); if(x==-1) return -1; return qpow(g,x,P); } int main(){ int T; scanf("%d",&T); for(;T>0;T--){ LL P,n,A; scanf("%lld%lld%lld",&P,&n,&A); LL X=work(P,n,A); printf("%lld\n",X); } return 0; }