Полезная функция для целочисленной арифметики: вычисление n^p (mod m) (т.е. остатка от деления n^p на m, кто не в курсе). Перимущества перед таким способом вычисления n*n*...*n % m :
1) Скорость вычисления. В обычном способе требуется p-1 операция умножения. В представленном — порядка log2(p).
2) Удобность в плане отсутствия переполнения типов.
//----------------------------------
// Вычисление n^p (mod m)
//----------------------------------
int PowerIntMod(int n, int p, int m)
{
int t, res;
for(t=n, res=p%2?t:1, p>>=1; p>0; p>>=1)
{
t = (int)fmodl(t*t, m);
if(p%2)
res = (int)fmodl(res*t, m);
}
return res;
};
Пример использования (представьте вычисление "тупым" способом):
int main()
{
int res = PowerIntMod(313, 217, 7);
cout<<res<<endl;
return 0;
}
Идея такая:
Раскладываем p в двоичном виде: b_(k-1) ... b_0. Наша цель посчитать
r=n^( 2^b_(k-1)+...2^b_0 )=n^(2^b_(k-1))*...*n^(2^b_0). Для этого достаточно вычислить каждый сомножитель, а это делается очень быстро. В общем виде не удобно писать, поэтому приведу пример.
Считаем n^45.
n^45=n^(b101101)=n^(32+8+4+1)=n^32*n^8*n^4*n^1
Теперь посчитаем все сомножители. Делать это будем так:
1) n^1=n
2) n^2=n^1*n^1
3) n^4=n^2*n^2
4) n^8=n^4*n^4
5) n^16=n^8*n^8
6) n^32=n^16*n^16