結果

問題 No.981 一般冪乗根
ユーザー 37zigen37zigen
提出日時 2020-02-08 09:57:15
言語 Java21
(openjdk 21)
結果
AC  
実行時間 870 ms / 6,000 ms
コード長 1,902 bytes
コンパイル時間 2,504 ms
コンパイル使用メモリ 77,836 KB
実行使用メモリ 46,432 KB
最終ジャッジ日時 2024-04-18 03:06:40
合計ジャッジ時間 56,671 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 275 ms
45,092 KB
testcase_01 AC 287 ms
45,080 KB
testcase_02 AC 293 ms
45,500 KB
testcase_03 AC 285 ms
45,008 KB
testcase_04 AC 281 ms
44,980 KB
testcase_05 AC 274 ms
45,032 KB
testcase_06 AC 274 ms
45,272 KB
testcase_07 AC 270 ms
45,216 KB
testcase_08 AC 276 ms
45,160 KB
testcase_09 AC 273 ms
45,100 KB
testcase_10 AC 272 ms
44,836 KB
testcase_11 AC 277 ms
45,116 KB
testcase_12 AC 276 ms
45,360 KB
testcase_13 AC 280 ms
45,240 KB
testcase_14 AC 276 ms
44,908 KB
testcase_15 AC 272 ms
45,032 KB
testcase_16 AC 275 ms
44,956 KB
testcase_17 AC 264 ms
45,164 KB
testcase_18 AC 271 ms
45,364 KB
testcase_19 AC 275 ms
44,852 KB
testcase_20 AC 271 ms
44,868 KB
testcase_21 AC 277 ms
45,192 KB
testcase_22 AC 272 ms
44,864 KB
testcase_23 AC 274 ms
45,280 KB
testcase_24 AC 271 ms
45,232 KB
testcase_25 AC 273 ms
44,968 KB
testcase_26 AC 279 ms
45,312 KB
testcase_27 AC 265 ms
45,040 KB
testcase_28 AC 870 ms
46,432 KB
evil_60bit1.txt WA -
evil_60bit2.txt WA -
evil_60bit3.txt WA -
evil_hack AC 132 ms
41,528 KB
evil_hard_random WA -
evil_hard_safeprime.txt WA -
evil_hard_tonelli0 WA -
evil_hard_tonelli1 WA -
evil_hard_tonelli2 WA -
evil_hard_tonelli3 WA -
evil_sefeprime1.txt WA -
evil_sefeprime2.txt WA -
evil_sefeprime3.txt WA -
evil_tonelli1.txt WA -
evil_tonelli2.txt WA -
権限があれば一括ダウンロードができます

ソースコード

diff # 

import java.io.PrintWriter;
import java.util.Arrays;
import java.util.Scanner;

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

	void run() {
		Scanner sc = new Scanner(System.in);
		PrintWriter pw = new PrintWriter(System.out);
        int T=sc.nextInt();
        for(int i=0;i<T;++i){
			long p=sc.nextLong();
			long k=sc.nextLong();
			long a=sc.nextLong();
			long kthroot = kth_root(a,k,p);
			//pw.println(kthroot);
			System.out.println(kthroot);
        }
        pw.close();
	}
	
	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;
		a=pow(a,inv(k/g,(p-1)/g),p);
		for(long div=2;div*div<=g;++div) {
			int sz=0;
			while(g%div==0) {
				g/=div;
				++sz;
			}
			if(sz>0) {
				long b=peth_root(a, div,sz, p);
				a=b;
			}
		}
		if(g>1)a=peth_root(a,g,1,p);
		return a;
	}

	long peth_root(long a,long p, long e, long mod) {
		long q=mod-1;
		int s=0;
		while(q%p==0){q/=p;++s;}
		long pe=pow(p,e,mod);
		long ans=pow(a,((pe-1)*inv(q,pe)%pe*q+1)/pe,mod);
		long c=2;
		while(pow(c,(mod-1)/p,mod)==1)++c;
		c=pow(c,q,mod);
		while(true){
			long err=pow(ans,pe,mod)*inv(a,mod)%mod;
			int bit=s-cnt(err,p,mod);//(hoge)p^bit
			if(bit==s)break;
			ans=ans*pow(c,pow(p,bit-e,mod),mod)%mod;
		}
		return ans;
	}
	
	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<0?u+p:u;
	}
	
	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