10692 Huge Mods
問題
a^b^c^d^... mod mの値が何になるか？
考え方
aとmが互いに素ならばオイラーのφ関数を使って、指数部分は「b^c^d^... mod φ(m)」とみなすことができる。これを繰り返していくことで、指数部分の計算をすることができる。(特に、指数部がφ(m)に等しいときは0 mod φ(m)になるので、a^φ(m)=a^0=1 mod mになり、これはオイラーの定理)
問題は互いに素じゃないときで、m=m1*m2*...とmiとmjが互いに素になるように分解すると、中国剰余定理によりa^b^... mod m1, a^b^... mod m2,...を計算して、x=b1*(m/m1)*x1+b2*(m/m2)*x2+... mod mとすることができる(xiは、(m/mi)*xi=1 mod miの解)。
miのうちでaと共通の因数となっているものはbi=0になるので、共通因子を取り除いたものをm'とすると、「x=b'*(m/m')*x' mod m」が答えになる。
