結果

問題 No.981 一般冪乗根
ユーザー chocoruskchocorusk
提出日時 2020-02-08 20:38:32
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
MLE  
(最新)
AC  
(最初)
実行時間 -
コード長 3,098 bytes
コンパイル時間 1,582 ms
コンパイル使用メモリ 117,840 KB
実行使用メモリ 609,696 KB
最終ジャッジ日時 2024-10-09 15:08:53
合計ジャッジ時間 81,794 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

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

ソースコード

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;
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 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<> rnd(1, p-1);
    int i=0;
    ll qi=1;
    while(i<s-e){
        ll v=rnd(mt);
        ll rv=powmod(v, r, p);
        if(powmod(rv, qs/q, p)==1) continue;
        rv=powmod(rv, qi, p);
        bool dame=1;
        for(ll j=0; j<q; j++){
            if(powmod(powmod(at, qp, p)*inva%p, qs/qp/qi/q, p)==1){
                dame=0;
                break;
            }
            (at*=rv)%=p;
        }
        if(dame) return -1;
        i++;
        qi*=q;
    }
    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;
    cin>>t;
    for(int i=0; i<t; i++){
        ll p, k, a;
        cin>>p>>k>>a;
        cout<<solve(p, k, a)<<endl;
    }
    return 0;
}
0