結果

問題 No.2993 冪乗乗 mod 冪乗
ユーザー 👑 testestest
提出日時 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
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 30 TLE * 1
権限があれば一括ダウンロードができます

ソースコード

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