Полезная функция для целочисленной арифметики: вычисление 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