AtCoder Regular Contest 111 A - Simple Math 2

問題リンク

解説

中学1年生になりましょう

(a M + b) (c M + d) = (acM + ad + bc) M + bd

です。

欲しいのは

10 ^ N = p M + q としたときの p でこれは↑の式を適宜modを取っていきながら繰り返し二乗法で展開すれば、計算量は O(\log n) です

提出コード

atcoder.jp