整数高速べき乗剰余

整数高速べき乗余剰,複雑度O(lgN),素朴アルゴリズムO(N)
32ビットMODテンプレート

int getPow(__int64 a, __int64 x, int MOD)  /* return a^x   :   */
{
	__int64 t = ( a % MOD);
	__int64 ans = 1;
	for(int i=0; (1<<i)<=x; ++i)
	{
		if(x & (1 << i)) ans *= t;
		if( ans >= MOD) ans %= MOD;
		t *= t;
		if( t >= MOD ) t %= MOD;
	}
	return (int)ans;
}

64ビットMODテンプレート

inline long long mul(long long a, long long b, long long MOD)/* 64 b   2   */
{
	long long ret = 0, temp = a % MOD; /*        */
	while( b )
	{
		if( b&1 ) if( (ret += temp) >= MOD ) ret -= MOD;
		if( (temp <<= 1) >= MOD ) temp -= MOD;
		b >>= 1;
	}
	return ret;
}
inline long long getPow(long long a, long long b, long long MOD)
{
    long long ret = 1 % MOD;
    while( b )
    {
        if( b&1 ) ret = mul( ret, a, MOD );
        a = mul( a, a, MOD );
        b >>= 1;
    }
    return ret;
}