結果

問題 No.2993 冪乗乗 mod 冪乗
ユーザー 👑 testestesttestestest
提出日時 2023-11-08 23:00:42
言語 PyPy3
(7.3.15)
結果
TLE  
(最新)
AC  
(最初)
実行時間 -
コード長 1,668 bytes
コンパイル時間 314 ms
コンパイル使用メモリ 82,200 KB
実行使用メモリ 159,708 KB
最終ジャッジ日時 2024-12-19 16:20:12
合計ジャッジ時間 40,917 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 TLE -
testcase_01 AC 53 ms
56,860 KB
testcase_02 AC 50 ms
55,832 KB
testcase_03 AC 49 ms
54,848 KB
testcase_04 AC 51 ms
55,764 KB
testcase_05 AC 50 ms
55,544 KB
testcase_06 AC 66 ms
64,256 KB
testcase_07 AC 179 ms
77,888 KB
testcase_08 AC 66 ms
63,892 KB
testcase_09 AC 66 ms
65,168 KB
testcase_10 AC 61 ms
62,920 KB
testcase_11 AC 490 ms
77,316 KB
testcase_12 AC 531 ms
77,180 KB
testcase_13 AC 422 ms
77,332 KB
testcase_14 AC 429 ms
77,232 KB
testcase_15 AC 511 ms
77,148 KB
testcase_16 AC 540 ms
78,112 KB
testcase_17 AC 571 ms
77,612 KB
testcase_18 AC 536 ms
78,064 KB
testcase_19 AC 551 ms
77,428 KB
testcase_20 AC 507 ms
77,516 KB
testcase_21 AC 533 ms
77,232 KB
testcase_22 AC 564 ms
77,300 KB
testcase_23 AC 552 ms
77,380 KB
testcase_24 AC 979 ms
98,916 KB
testcase_25 AC 826 ms
88,664 KB
testcase_26 AC 584 ms
77,740 KB
testcase_27 AC 548 ms
77,708 KB
testcase_28 AC 525 ms
77,144 KB
testcase_29 AC 3,079 ms
101,056 KB
testcase_30 AC 2,315 ms
159,708 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

"""
① n十分大でM^{B^n}=1 mod p が必要
→　ord(M)|B^n が必要
→　ord(M)≦p≦B≦10^6なのでn≦log2(10^6)≦20まで調べれば十分。最小のnをn_pとおく
② ord_p(B)=e、B=B'p^eとおく。M^{B^n}=(M^{B'^n})^{p^{en}}であり、
一般に(1+xp^n)^p=1+x'p^{n+1}である（二項定理より）ことと、
n_pの定義からn≧n_pでM^{B'^n}=1 mod pであることから、
n≧n_pでM^{B^n}=1 mod p^{en}
③ あるn≧N+1に対してaが存在してM^{B^n}=1+aB^n mod B^{n+N}となるなら、
そのaで任意のn'≧nに対しても成り立つ（二項定理より）
④ ②③とCRTよりmax(max(n_p),N+1)乗すれば十分。max(n_p)≦20、N≦log2(10^6)<20なので高々20乗
→　実際に計算すれば良い(?)

実はmax(max(n_p),N)乗でも正しい。このとき仮定を満たさないのは③だけだが、
実際に③が成り立たないためにはBが偶数かつaが奇数であることが必要であり、
②の最後の式がmod p^{en+1}で成り立っていることを思い出すとそのようなことはあり得ない。
"""

from functools import cache
@cache
def factor(n):
	# return {p:prime | n%p==0}
	ret=[]
	for p in range(2,n+1):
		if p*p>n: break
		if n%p==0:
			ret.append(p)
			while n%p==0: n//=p
	if n!=1: ret.append(n)
	return ret

def g(m,b,p):
	# return min{n | m**(b**n)%p==1}
	crr=m%p
	for n in range(22):
		if crr==1: break
		crr=pow(crr,b,p)
	return n

def solve(B,N,M):
	primes=factor(B)
	e=max(g(M,B,p) for p in primes)
	if e==21: return -1
	E=max(N,e)
	temp=pow(M,B**E,B**(E+N))
	return temp//(B**E)

T=int(input())
for _ in range(T):
	print(solve(*map(int,input().split())))
0