読者です 読者をやめる 読者になる 読者になる

kmjp's blog

競技プログラミング参加記です

yukicoder : No.251 大きな桁の復習問題(1)

yukicoder

No.255が時間内にバグとりきれなくて残念。
http://yukicoder.me/problems/392

問題

最大100000桁の整数N,Mが与えられる。
 N^M mod 129402307を答えよ。

問題

p=129402307とする。
pは素数なのでフェルマーの小定理より、 N^M \equiv (N\%p)^{(M\%(p-1))}となる。

まぁ多倍長のpowmodが使える言語なら、それを呼ぶだけなんだけどね。

N=input()
M=input()

print pow(N,M,129402307)

まとめ

ん、(1)?
これは…。

広告を非表示にする