torus711 のアレ

主に競技プログラミングの問題について書きます.PC 以外だと数式が表示されないかもしれないです

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

問題概要

 整数 $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;
}