結果

問題 No.981 一般冪乗根
ユーザー ace_amuroace_amuro
提出日時 2021-01-22 17:41:52
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 3,301 ms / 6,000 ms
コード長 3,297 bytes
コンパイル時間 800 ms
コンパイル使用メモリ 81,524 KB
実行使用メモリ 22,660 KB
最終ジャッジ日時 2023-08-27 11:09:58
合計ジャッジ時間 144,023 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge14
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2,777 ms
22,260 KB
testcase_01 AC 2,839 ms
22,660 KB
testcase_02 AC 2,582 ms
19,424 KB
testcase_03 AC 2,535 ms
19,176 KB
testcase_04 AC 2,505 ms
19,412 KB
testcase_05 AC 846 ms
19,216 KB
testcase_06 AC 880 ms
19,216 KB
testcase_07 AC 892 ms
19,340 KB
testcase_08 AC 919 ms
19,292 KB
testcase_09 AC 928 ms
19,424 KB
testcase_10 AC 957 ms
19,192 KB
testcase_11 AC 925 ms
19,204 KB
testcase_12 AC 939 ms
19,308 KB
testcase_13 AC 912 ms
19,156 KB
testcase_14 AC 987 ms
19,104 KB
testcase_15 AC 891 ms
19,200 KB
testcase_16 AC 905 ms
19,280 KB
testcase_17 AC 976 ms
19,192 KB
testcase_18 AC 903 ms
19,208 KB
testcase_19 AC 880 ms
19,344 KB
testcase_20 AC 918 ms
19,224 KB
testcase_21 AC 887 ms
19,284 KB
testcase_22 AC 867 ms
19,112 KB
testcase_23 AC 962 ms
19,272 KB
testcase_24 AC 993 ms
19,284 KB
testcase_25 AC 3,098 ms
19,272 KB
testcase_26 AC 3,301 ms
19,280 KB
testcase_27 AC 794 ms
19,100 KB
testcase_28 AC 2,527 ms
19,180 KB
evil_60bit1.txt RE -
evil_60bit2.txt RE -
evil_60bit3.txt TLE -
evil_hack AC 8 ms
19,164 KB
evil_hard_random RE -
evil_hard_safeprime.txt TLE -
evil_hard_tonelli0 RE -
evil_hard_tonelli1 RE -
evil_hard_tonelli2 RE -
evil_hard_tonelli3 RE -
evil_sefeprime1.txt TLE -
evil_sefeprime2.txt TLE -
evil_sefeprime3.txt TLE -
evil_tonelli1.txt RE -
evil_tonelli2.txt RE -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#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=ans*a%mod;//ans=qmul(ans,a,mod);
        a=a*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 ((b/d)*x%(p/d)+p/d)%(p/d);
    //(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=r*a%p;//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=t*am%p;//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;
}
0