На сайте TopCoder появилась очередная статья из раздела Feature Article – Primality Testing : Non-deterministic Algorithms, в начале которой описан любопытный метод вычисления произведения a * b % c, если все числа 64-битные и длинная арифметика не используется. Метод похож на быстрое возведение в степень и работает за O(log b).

Вот, собственно, код, немного оптимизированный мною:

long long multiply(long long a, long long b, long long c) {
   long long x = 0, y = a % c;
   b %= c;
   while (b > 0) {
       if (b & 1) {
           x += y;
           if (x >= c) x -= c;
       }
       y <<= 1;
       if (y >= c) y -= c;
       b >>= 1;
   }
   return x;
}