結果

問題 No.981 一般冪乗根
ユーザー chocoruskchocorusk
提出日時 2020-02-11 06:28:40
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 10 ms / 6,000 ms
コード長 3,658 bytes
コンパイル時間 3,003 ms
コンパイル使用メモリ 125,100 KB
実行使用メモリ 10,144 KB
最終ジャッジ日時 2024-10-09 23:28:16
合計ジャッジ時間 75,067 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 6 ms
10,144 KB
testcase_01 AC 6 ms
6,820 KB
testcase_02 AC 6 ms
6,816 KB
testcase_03 AC 6 ms
6,816 KB
testcase_04 AC 5 ms
6,816 KB
testcase_05 AC 5 ms
6,820 KB
testcase_06 AC 5 ms
6,816 KB
testcase_07 AC 6 ms
6,816 KB
testcase_08 AC 4 ms
6,816 KB
testcase_09 AC 5 ms
6,816 KB
testcase_10 AC 5 ms
6,820 KB
testcase_11 AC 5 ms
6,820 KB
testcase_12 AC 5 ms
6,820 KB
testcase_13 AC 5 ms
6,816 KB
testcase_14 AC 5 ms
6,820 KB
testcase_15 AC 5 ms
6,820 KB
testcase_16 AC 4 ms
6,816 KB
testcase_17 AC 5 ms
6,816 KB
testcase_18 AC 5 ms
6,816 KB
testcase_19 AC 5 ms
6,820 KB
testcase_20 AC 4 ms
6,816 KB
testcase_21 AC 4 ms
6,816 KB
testcase_22 AC 5 ms
6,816 KB
testcase_23 AC 5 ms
6,820 KB
testcase_24 AC 4 ms
6,820 KB
testcase_25 AC 4 ms
6,816 KB
testcase_26 AC 5 ms
6,816 KB
testcase_27 AC 3 ms
6,816 KB
testcase_28 AC 10 ms
6,816 KB
evil_60bit1.txt AC 13 ms
6,816 KB
evil_60bit2.txt AC 15 ms
6,820 KB
evil_60bit3.txt AC 14 ms
6,820 KB
evil_hack AC 2 ms
6,816 KB
evil_hard_random AC 14 ms
6,816 KB
evil_hard_safeprime.txt AC 14 ms
6,820 KB
evil_hard_tonelli0 TLE -
evil_hard_tonelli1 AC 3,365 ms
6,820 KB
evil_hard_tonelli2 AC 186 ms
6,820 KB
evil_hard_tonelli3 TLE -
evil_sefeprime1.txt AC 11 ms
6,816 KB
evil_sefeprime2.txt AC 11 ms
6,816 KB
evil_sefeprime3.txt AC 11 ms
6,816 KB
evil_tonelli1.txt AC 4,335 ms
6,820 KB
evil_tonelli2.txt AC 4,345 ms
10,276 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <cstdio>
#include <cstring>
#include <iostream>
#include <string>
#include <cmath>
#include <bitset>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <algorithm>
#include <complex>
#include <unordered_map>
#include <unordered_set>
#include <random>
#include <cassert>
#include <fstream>
#include <utility>
#include <functional>
#include <time.h>
#include <stack>
#include <array>
#define popcount __builtin_popcount
using namespace std;
//typedef long long int ll;
using ll=__int128_t;
typedef pair<ll, int> P;
ll gcd(ll a, ll b){
    if(b==0) return a;
    return gcd(b, a%b);
}
ll powmod(ll a, ll k, ll mod){
    ll ap=a, ans=1;
    while(k){
        if(k&1){
            ans*=ap;
            ans%=mod;
        }
        ap=ap*ap;
        ap%=mod;
        k>>=1;
    }
    return ans;
}
ll inv(ll a, ll m){
    ll b=m, x=1, y=0;
    while(b>0){
        ll t=a/b;
        swap(a-=t*b, b);
        swap(x-=t*y, y);
    }
    return (x%m+m)%m;
}
vector<P> fac(ll x){
	vector<P> ret;
	for(ll i=2; i*i<=x; i++){
		if(x%i==0){
			int e=0;
			while(x%i==0){
				x/=i;
				e++;
			}
			ret.push_back({i, e});
		}
	}
	if(x>1) ret.push_back({x, 1});
	return ret;
}
mt19937_64 mt(334);
ll solve1(ll p, ll q, int e, ll a){
    int s=0;
    ll r=p-1;
    ll qs=1;
    while(r%q==0){
        r/=q;
        qs*=q;
        s++;
    }
    ll qp=1;
    for(int i=0; i<e; i++) qp*=q;
    ll d=qp-inv(r%qp, qp);
    ll t=(d*r+1)/qp;
    ll at=powmod(a, t, p), inva=inv(a, p);
    if(e>=s){
        if(powmod(at, qp, p)!=a) return -1;
        else return at;
    }
    uniform_int_distribution<long long> rnd(1, p-1);
    ll rv;
    while(1){
        rv=powmod(rnd(mt), r, p);
        if(powmod(rv, qs/q, p)!=1) break;
    }
    int i=0;
    ll qi=1;
    ll sq=1;
    while(sq*sq<q) sq++;
    while(i<s-e){
        ll qq=qs/qp/qi/q;
        vector<P> v(sq);
        ll rvi=powmod(rv, qp*qq*(p-2)%(p-1), p), rvp=powmod(rv, sq*qp*qq, p);
        ll x=powmod(powmod(at, qp, p)*inva%p, qq*(p-2)%(p-1), p), y=1;
        for(int j=0; j<sq; j++){
            v[j]=P(x, j);
            (x*=rvi)%=p;
        }
        sort(v.begin(), v.end());
        ll z=-1;
        for(int j=0; j<sq; j++){
            int l=lower_bound(v.begin(), v.end(), P(y, 0))-v.begin();
            if(v[l].first==y){
                z=v[l].second+j*sq;
                break;
            }
            (y*=rvp)%=p;
        }
        if(z==-1) return -1;
        (at*=powmod(rv, z, p))%=p;
        i++;
        qi*=q;
        rv=powmod(rv, q, p);
    }
    return at;
}
ll solve(ll p, ll k, ll a){
    if(p==2 || a==1) return 1;
    ll a1=a;
    ll g=gcd(p-1, k);
    ll c=inv(k/g%((p-1)/g), (p-1)/g);
    a=powmod(a, c, p);
    if(g==1){
        if(powmod(a, k, p)==a1) return a;
        else return -1;
    }
    vector<P> f=fac(g);
    ll ret=1;
    ll gp=1;
    for(auto r:f){
        ll qp=1;
        for(int i=0; i<r.second; i++) qp*=r.first;
        ll x=solve1(p, r.first, r.second, a);
        if(x==-1) return -1;
        if(gp==1){
            ret=x;
            gp*=qp;
            continue;
        }
        ll s=inv(gp%qp, qp), t=(1-gp*s)/qp;
        if(t>=0) ret=powmod(ret, t, p);
        else ret=powmod(inv(ret, p), -t, p);
        if(s>=0) x=powmod(x, s, p);
        else x=powmod(inv(x, p), -s, p);
        (ret*=x)%=p;
        gp*=qp;
    }
    if(powmod(ret, k, p)!=a1) return -1;
    return ret;
}
int main()
{
    int t;
    scanf("%d", &t);
    for(int i=0; i<t; i++){
        long long p, k, a;
        scanf("%lld %lld %lld", &p, &k, &a);
        long long ans=solve(p, k, a);
        printf("%lld\n", ans);
    }
    return 0;
}
0