結果

問題 No.981 一般冪乗根
ユーザー chocorusk
提出日時 2020-02-08 17:28:22
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 5,273 ms / 6,000 ms
コード長 3,282 bytes
コンパイル時間 1,655 ms
コンパイル使用メモリ 132,084 KB
実行使用メモリ 10,152 KB
最終ジャッジ日時 2024-10-09 15:11:04
合計ジャッジ時間 129,349 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 30 RE * 1 TLE * 4 MLE * 9
権限があれば一括ダウンロードができます

ソースコード

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(a==0) return b;
	if(b==0) return a;
	if(a<0) a=-a;
	if(b<0) b=-b;
	const int s=__builtin_ctzll(a|b);
	a>>=__builtin_ctzll(a);
	while(b){
		b>>=__builtin_ctzll(b);
		if(a>b) swap(a, b);
		b-=a;
	}
	return a<<s;
}
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;
}
mt19937 mt(334);
bool is_prime(ll n){
	if(n<=1 || !(n&1)) return (n==2);
	ll d=n-1;
	int k=0;
	while(!(d&1)){
		d>>=1;
		k++;
	}
	uniform_int_distribution<> rnd(1, n-1);
	for(int z=0; z<10; z++){
		ll a=rnd(mt);
		if(a==0) continue;
		bool comp=1;
		ll ap=powmod(a, d, n);
		if(ap==1 || ap==n-1) continue;
		for(int r=1; r<k; r++){
			ap=ap*ap%n;
			if(ap==n-1){
				comp=0;
				break;
			}
		}
		if(comp) return false;
	}
	return true;
}
ll rho(ll n, ll& c){
	if(!(n&1)) return 2;
	while(1){
		ll x=2, y=2, d=1;
		while(d==1){
			x=(x*x+c)%n;
			y=(y*y+c)%n;
			y=(y*y+c)%n;
			d=gcd(abs(x-y), n);
		}
		if(d==n){
			c++;
			continue;
		}
		return d;
	}
}
vector<pair<ll, int>> factorize(ll n){
	if(n<=1){
		vector<pair<ll, int>> ret;
		return ret;
	}
	map<ll, int> mp;
	vector<ll> v(1, n);
	ll c=1;
	while(!v.empty()){
		ll x=v.back();
		v.pop_back();
		if(is_prime(x)){
			mp[x]++;
			continue;
		}
		ll p=rho(x, c);
		v.push_back(p);
		v.push_back(x/p);
	}
	vector<pair<ll, int>> ret;
	for(auto p:mp) ret.push_back(p);
	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;
		for(int i=0; i<e; i++){
			rp*=r;
			if(powmod(a, (p-1)/rp, p)!=1){
				break;
			}
			d*=r;
		}
	}
	return (p-1)/d;
}
ll root(ll p){
	vector<P> v=factorize(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