The product of numbers of order 10 ^ 9 modulo

Try this:

static int MulPeasant(int a, int b, int n) { a = a % n; // не нужно, если гарантированно a < n b = b % n; // не нужно, если гарантированно b < n int acc = 0; while (b > 0) { if ((b & 1) != 0) acc = (acc + a) % n; a = (a * 2) % n; b >>= 1; } return acc; } 

The expression (acc + a * b) % n is a loop invariant.

Should work if n < MAXINT/2 .

(If I am not mistaken, this is the so-called " Russian peasant method ").

For the case of arbitrary n small modification is appropriate:

 static int MulPeasant(int a, int b, int n) { a = a % n; // не нужно, если гарантированно a < n b = b % n; // не нужно, если гарантированно b < n int acc = 0; while (b > 0) { if ((b & 1) != 0) acc = SafeAdd(acc, a, n); a = SafeAdd(a, a, n); b >>= 1; } return acc; } static int SafeAdd(int x, int y, int n) { if (x <= MAXINT - y) // проверка на переполнение сложения { int result = x + y; // x, y < n, x + y < 2n. (x + y) mod n равно или x + y, return (result >= n) ? (result - n) : result; // или x + y - n } else // в этом случае x + y > MAXINT >= n, но x + y < n + n = 2n { // значит (x + y) mod n = x + y - n return x - (n - y); // n - y > 0, вычитаем два положительных числа меньших n } } 

You can still organize the bitwise multiplication:

 const int halfbits = sizeof(int) * 8 / 2; const int halfbase = (1 << halfbits); const int lomask = halfbase - 1; static int MulDigits(int a, int b, int n) { int reducedbase = halfbase % n; int reducedbasesquare = (reducedbase * reducedbase) % n; int ah = a >> halfbits, al = a & lomask; int bh = b >> halfbits, bl = b & lomask; int ll = (al * bl) % n, lh = (((ah * bl) % n) * reducedbase) % n, hl = (((al * bh) % n) * reducedbase) % n, hh = (((ah * bh) % n) * reducedbasesquare) % n; return SafeAdd( SafeAdd(ll, lh, n), SafeAdd(hl, hh, n), n); } 

(If your n is the same all the time, the reducedbase and reducedbasesquare can be precomputed.)

In general, read the Art of Programming , chapters 4.3.2 and 4.3.3.