結果
| 問題 | No.981 一般冪乗根 |
| ユーザー |
 ace_amuro
|
| 提出日時 | 2021-01-22 17:33:45 |
| 言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 3,214 bytes |
| コンパイル時間 | 791 ms |
| コンパイル使用メモリ | 82,020 KB |
| 実行使用メモリ | 23,576 KB |
| 最終ジャッジ日時 | 2023-08-27 10:02:33 |
| 合計ジャッジ時間 | 17,863 ms |
|
ジャッジサーバーID （参考情報） |
judge12 / judge15 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| 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;
}