結果

問題 No.981 一般冪乗根
ユーザー 37zigen
提出日時 2020-02-01 04:05:06
言語 Java
(openjdk 23)
結果
TLE  
(最新)
AC  
(最初)
実行時間 -
コード長 1,958 bytes
コンパイル時間 2,533 ms
コンパイル使用メモリ 79,768 KB
実行使用メモリ 65,332 KB
最終ジャッジ日時 2024-10-09 14:02:05
合計ジャッジ時間 17,673 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other TLE * 1 -- * 43
権限があれば一括ダウンロードができます

ソースコード

diff # 

import java.util.*;
import java.io.*;

class Main {
	public static void main(String[] args) throws Exception {
		new Main().run();
	}

	void run() {
		Scanner sc = new Scanner(System.in);
        int T=sc.nextInt();
        for(int i=0;i<T;++i){
			long p=sc.nextLong();
			long k=sc.nextLong();
			long a=sc.nextLong();
			long root = kth_root(a,k,p);
			System.out.println(root);
        }
	}
	
	long kth_root(long a,long k,long p){
		long g=gcd(k,p-1);
		if(pow(a,(p-1)/g,p)!=1)return -1;
		long root=primitiveRoot(p);
		long y=log(a,root,p);
		long z=inv(k/g,(p-1)/g)*(y/g)%(p-1);
		return pow(root,z,p);
	}
		
	// a=g^x mod p
	long log(long a,long g,long p){
		int v=(int)Math.sqrt(p)+1;
		//g^{qv+r}=a
		HashMap<Long,Integer> map=new HashMap<>();
		long mul=1;
		for(int r=0;r<=v;++r){
			map.put(mul,r);
			mul=mul*g%p;
		}
		long g2=pow(inv(g,p),v,p);
		mul=1;
		for(int q=0;q<=v;++q){
			if(map.containsKey(a*mul%p)){
				return (q*v%(p-1)+map.get(a*mul%p))%(p-1);
			}
			mul=mul*g2%p;
		}
		throw new AssertionError();
	}
	
	long primitiveRoot(long p){
		for(long i=1;i<p;++i){
			if(isPrimitiveRoot(i,p))return i;
		}
		throw new AssertionError();
	}
	
	boolean isPrimitiveRoot(long a,long p){
		boolean ret=true;
		for(long div=2;div*div<=p-1;++div){
			ret&=pow(a,div,p)!=1;
			ret&=pow(a,(p-1)/div,p)!=1;
			if(!ret)return false;
		}
		return true;
	}
	
	int cnt(long a,long base,long p){
		int ret=0;
		while(a!=1){
			a=pow(a,base,p);
			++ret;
		}
		return ret;
	}
	
	long inv(long a,long p){
		a%=p;
		long u=1,v=0;
		long b=p;
		while(b>0) {
			long q=a/b;
			a%=b;
			u-=v*q%p;
			u%=p;
			{
				u^=v;v^=u;u^=v;
				a^=b;b^=a;a^=b;
			}
		}
		return (u%p+p)%p;
	}
	
	long pow(long a,long n,long p){
		n%=p-1;
		long r=1;
		for(;n>0;n>>=1,a=a*a%p)if(n%2==1)r=r*a%p;
		return r;
	}
	
	long gcd(long a,long b) {
		return a==0?b:gcd(b%a,a);
	}
	
	static void tr(Object... objects) {
		System.out.println(Arrays.deepToString(objects));
	}

}
0