a^n%kのlognのアルゴリズム
459 ワード
long long Cal ( long long a, long long n, long long k )
{
if ( !a ) // a == 0 0
return 0;
int r = 1; // r
while ( n-- )
{
if ( n & 1 ) // n
r = r * a % k;
else
{
n >>= 1; // a^n = a^2^sqrt(n)
a *= a;
a %= k;
}
}
return r;
}