結果

問題 No.981 一般冪乗根
ユーザー chocorusk
提出日時 2020-02-08 17:19:01
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 5,581 ms / 6,000 ms
コード長 2,337 bytes
コンパイル時間 1,573 ms
コンパイル使用メモリ 120,728 KB
実行使用メモリ 10,144 KB
最終ジャッジ日時 2024-10-09 15:00:15
合計ジャッジ時間 156,364 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 30 RE * 7 TLE * 6 MLE * 1
権限があれば一括ダウンロードができます

ソースコード

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<int, 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;
}
ll discretelog(ll x, ll y, ll m){
	ll d=1;
	while(d*d<m) d++;
	vector<P> v(d);
	ll invx=inv(x, m);
	ll y1=y;
	for(int i=0; i<d; i++){
		v[i]=P(y1, i);
		(y1*=invx)%=m;
	}
	sort(v.begin(), v.end());
	ll xd=powmod(x, d, m);
	ll q=1;
	for(int i=0; i<d; i++){
		int k=lower_bound(v.begin(), v.end(), P(q, 0))-v.begin();
		if(v[k].first==q){
			return i*d+v[k].second;
		}
		(q*=xd)%=m;
	}
    return -1;
}
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;
}
ll order(ll p, ll a, vector<P> v){
	ll d=1;
	for(auto q:v){
		ll r=q.first; int e=q.second;
		ll rp=1;
		bool myon=0;
		for(int i=1; i<=e; i++){
			rp*=r;
			if(powmod(a, (p-1)/rp, p)!=1){
				d*=(rp/r);
				myon=1;
				break;
			}
		}
		if(!myon) d*=rp;
	}
	return (p-1)/d;
}
ll root(ll p){
	vector<P> v=fac(p-1);
	for(ll r=2; ; r++){
		if(order(p, r, v)==p-1){
			return r;
		}
	}
}
ll solve(ll p, int k, ll a){
	if(p==2){
		return 1;
	}
	if(a==1){
		return 1;
	}
	ll r=root(p);
	ll d=discretelog(r, a, p);
	ll g=gcd(k, p-1);
	if(d%g!=0){
		return -1;
	}
	d/=g;
	return powmod(r, inv(k/g, (p-1)/g)*d%((p-1)/g), p);
}
int main()
{
	int t;
	cin>>t;
	while(t--){
		ll p, a;
		int k;
		cin>>p>>k>>a;
        cout<<solve(p, k, a)<<endl;
	}
	return 0;
}
0