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

問題文

　http://yukicoder.me/problems/392

問題概要

　整数 $N$, $M $ が与えられる．$N^M $ を求めよ．
　$0 \leq N, M \leq 10^{100000}$

解法

　冪指数が大きい場合の冪乗を（$\bmod$ で）計算するアルゴリズムとして，「反復二乗法」というものがよく知られています．これは，$A^X$ を計算するとき，$X$ の 2 進展開を考えて計算量を減らす手法です．
　詳しく述べます．まず，任意の整数 $X$ を $X = \sum{ 2^i \times k_i }$ ( $k_i \in \{ 0, 1 \}$ ) という 2 冪の和の形で表現することができます．また，指数法則を踏まえると，任意の $Y$, $Z$ に対して $A^Y \times A^Z = A^{ Y + Z }$ です．従って，$A^X$ を，先程の 2 進展開のときと同様の $k$ を用いて $A^X = \prod{ A^{ 2^i \times k_i } }$ と表すことができます．このとき，$\prod$ の計算中に必要になるのは $A^{ 2^i }$ という形の値です．同じく指数法則より $A^{ 2^{ i + 1 } } = A^{ 2^i } \times A^{ 2^i }$ なので，自乗を $O( \log A )$ 回計算することで，必要になる $A^{ 2^i }$ を列挙できます．また，$k_i$ は $X$ を順次 2 で割っていけば求ります．$k_i = 1$ となる $i$ のところだけを選んで掛け合わせれば $A^X$ を $O( \log X )$ 時間で求められるというのが，反復二乗法です．
　さて，反復二乗法の考え方を応用することで，この問題を解くことができます．$N^M $ を計算するにあたり，まずは $M $ の 10 進展開を考えます（要するに入力で与えられるのと同じ形式です）．このとき，$M $ を $M = \sum{ 10^i \times k_i }$ ( $k_i \in [ 0, 9 ]$ ) という具合に 10 の冪乗の和で表すことができます．従って，先程と同様に $N^M = \prod{ A^{ 10^i \times k_i } }$ とすることができて，同様の議論により，$N^{ 10^i }$ と表される整数を列挙すれば，必要なものを掛け合わせることで $N^M $ を計算できます．$k_i$ というのは（下から）$i$ 桁目が $d$ なら $k_i = d$ となるので，こちらも既知な値となります．従って，計算に必要な値は全て容易に求めることができます．
　このアルゴリズムは，$M $ が正である間 $M $ を $\lfloor M / 10 \rfloor$ で置き換えることで実装できるので，$O( \log_{ 10 } M )$ 時間で走ります．
　また，$N$ の方の処理は，$N$ を上の桁から走査することで $\bmod$ での値を計算できます．

コード

using LL = long long;

#define REP2( i, n ) REP3( i, 0, n )
#define REP3( i, m, n ) for ( int i = ( int )( m ); i < ( int )( n ); ++i )
#define GET_REP( a, b, c, F, ... ) F
#define REP( ... ) GET_REP( __VA_ARGS__, REP3, REP2 )( __VA_ARGS__ )
#define FOR( e, c ) for ( auto &e : c )

#define SZ( v ) ( (int)( v ).size() )

constexpr int MOD = 129402307;

int main()
{
	cin.tie( 0 );
	ios::sync_with_stdio( false );

	string A, X;
	cin >> A >> X;

	LL a = 0;
	FOR( c, A )
	{
		a *= 10;
		a += c - '0';
		a %= MOD;
	}

	LL res = 1;
	for ( int i = SZ( X ) - 1; 0 <= i; --i )
	{
		const int D = X[i] - '0';

		REP( j , D )
		{
			( res *= a ) %= MOD;
		}

		LL na = 1;
		REP( j, 10 )
		{
			( na *= a ) %= MOD;
		}
		a = na;
	}
	cout << res << endl;

	return 0;
}