結果

問題 No.981 一般冪乗根
ユーザー chocorusk
提出日時 2020-02-07 21:49:31
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 5,716 ms / 6,000 ms
コード長 2,756 bytes
コンパイル時間 1,493 ms
コンパイル使用メモリ 124,272 KB
実行使用メモリ 57,116 KB
最終ジャッジ日時 2024-10-09 14:19:42
合計ジャッジ時間 188,456 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 30 TLE * 14
権限があれば一括ダウンロードができます

ソースコード

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 p=1%m;
    for(int i=0; i<=30; i++){
        if(p==y) return i;
        (p*=x)%=m;
    }
    ll g=gcd(x, m);
    ll m1=m;
    for(ll i=2; i*i<=g; i++){
        if(g%i==0){
            while(g%i==0) g/=i;
            while(m1%i==0) m1/=i;
        }
    }
    if(g>1){
        while(m1%g==0) m1/=g;
    }
    if(y%(m/m1)!=0) return -1;
    x%=m1, y%=m1;
    ll d=1;
    while(d*d<m1) d++;
    ll invx=inv(x, m1);
    unordered_map<ll, ll> mp; //yx^(-b)
    ll y1=y;
    for(ll i=0; i<d; i++){
        mp[y1]=i;
        (y1*=invx)%=m1;
        if(y1==y) break;
    }
    ll xd=powmod(x, d, m1);
    ll q=1%m1;
    for(ll i=0; i<d; i++){
        auto itr=mp.find(q);
        if(itr!=mp.end()){
            return i*d+itr->second;
        }
        (q*=xd)%=m1;
    }
    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