#419967 (Java21) No.981 一般冪乗根

• 問題: No.981 一般冪乗根
• ユーザー: 37zigen
• 提出日時: 2020-01-20 13:25:14
• 言語: Java21 (openjdk 21)
• 結果: WA
• 実行時間: -
• コード長: 2,886 bytes
• コンパイル時間: 3,174 ms
• コンパイル使用メモリ: 89,752 KB
• 実行使用メモリ: 54,808 KB
• 最終ジャッジ日時: 2024-04-17 19:51:58
• 合計ジャッジ時間: 42,895 ms
• ジャッジサーバーID （参考情報）: judge2 / judge4

入力	結果	実行時間; 実行使用メモリ
testcase_00	WA	-
testcase_01	WA	-
testcase_02	WA	-
testcase_03	WA	-
testcase_04	WA	-
testcase_05	WA	-
testcase_06	WA	-
testcase_07	WA	-
testcase_08	WA	-
testcase_09	WA	-
testcase_10	WA	-
testcase_11	WA	-
testcase_12	WA	-
testcase_13	WA	-
testcase_14	WA	-
testcase_15	WA	-
testcase_16	WA	-
testcase_17	WA	-
testcase_18	WA	-
testcase_19	WA	-
testcase_20	WA	-
testcase_21	WA	-
testcase_22	WA	-
testcase_23	WA	-
testcase_24	WA	-
testcase_25	WA	-
testcase_26	WA	-
testcase_27	WA	-
testcase_28	WA	-
evil_60bit1.txt	WA	-
evil_60bit2.txt	WA	-
evil_60bit3.txt	WA	-
evil_hack	RE	-
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	-

ソースコード

import java.io.BufferedReader;
import java.io.File;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;
import java.math.BigInteger;
import java.util.Arrays;
import java.util.Random;
import java.util.Scanner;

class Main {
	public static void main(String[] args) throws Exception {
		new Main().run();
//		new Main().generate();
//		new Main().judge(args[0]);
	}
	
	void judge(String args0) throws Exception {
		File file_in = new File(args0);
		BufferedReader br_in = new BufferedReader(new FileReader(file_in));
		Scanner sc = new Scanner(System.in);
		String[] vs=br_in.readLine().split(" ");
		long p = Integer.parseInt(vs[0]);
		long k = Integer.parseInt(vs[1]);
		long a = Integer.parseInt(vs[2]);
		long x = Integer.parseInt(sc.next());
		long g=gcd(k,p-1);
		if(pow(a,(p-1)/g,p)!=1) {
			assert(x==-1);
		}else {
			assert(pow(x,k,p)==a);
		}
		br_in.close();
	}
	

	void generate() {
		long p=-1;
		long k=-1;
		long a=-1;
		while(!(2<=p&&p<=1e9+7))p=BigInteger.probablePrime(20, new Random()).longValue();
		while(!(2<=k&&k<=1000))k=(int)(Math.random()*2000)%1000;
		while(!(2<=a&&a<p))a=(int)(Math.random()*p*2)%p;
		System.out.println(a+" "+k+" "+p);
	}
	
	void run() {
		Scanner sc = new Scanner(System.in);
		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;
		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, pow(div,sz,p), p);
				a=b;
			}
		}
		if(g>1)a=peth_root(a,g,p);
		return a;
	}
	
	long peth_root(long a,long k,long p) {
		long sz=p-1;
		int s=0;
		while(sz%k==0){sz/=k;++s;}
		long q1=sz;//q
		long q2=(p-1)/sz;
		long ans=pow(a,((k-1)*inv(q1,k)%k*q1+1)/k,p);
		long c=2;
		while(pow(c,(p-1)/k,p)==1){++c;}
		c=pow(c,q1,p);
		while(true){
			long err=pow(ans,k,p)*inv(a,p)%p;
			int bit=s-cnt(err,k,p);
			if(bit==s)break;
			if(bit==0)throw new AssertionError();
			ans=ans*pow(c,pow(k,bit-1,p),p)%p;
		}
		if(pow(ans,k,p)!=a)throw new AssertionError();
		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;
			}
		}
		//if(a!=1)throw new AssertionError();
		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));
	}

}