б% а где б очень большой
Нам дают два целых числа a а также b, a <= 100000, b < 10^250, Я хочу рассчитать b% а. Я нашел этот алгоритм, но не могу понять, как он работает.
int mod(int a, char b[])
{
int r = 0;
int i;
for(i=0;b[i];++i)
{
r=10*r +(b[i] - 48);
r = r % a;
}
return r;
}
Пожалуйста, объясните логику этого. Я знаю основные свойства модульной математики.
Благодарю.
Решение
Это довольно легко понять, если вы знаете модульную арифметику, выражение (b[n] + 10 * b[n - 1] + ... + 10^k * b[k] + ... + 10^n * b[0]) modulo a что технически первоначальное постановка задачи может быть упрощено до (...((b[0] modulo a) * 10 + b[1]) modulo a) * 10 + ... + b[n]) modulo a что делает ваш алгоритм.
Чтобы доказать, что они равны, мы можем вычислить коэффициент по модулю a до b[i] во втором выражении легко увидеть, что для b[i] точно будет n - i раз нам придется умножить его на 10 (последний, который n будет умножен на 0 раз, один перед ним 1 раз и так далее …). Так по модулю a это равно 10 ^ (n - i) который является тем же коэффициентом, прежде чем b[i] в первом выражении.
Таким образом, так как все коэффициенты перед b[i] в обоих выражениях будет равным, очевидно, что оба выражения равны (k_0 * b[0] + k_1 * b[1] ... + k_n * b[n]) по модулю a и, таким образом, они равны по модулю a,
48 это код для 0 цифра, так (b[i] - 48) это преобразование из символа в цифру.
Другие решения
В основном эта функция реализует Алгоритм Хорнера вычислить десятичное значение b,
Как объяснил @Predelnik, значение b является полиномом, коэффициенты которого являются цифрами b и переменная x является 10, Функция вычисляет модуль по каждой итерации, используя тот факт, что модуль совместим с сложением и умножением:
(a+b) % c = ((a%c) + (b%c)) % c
(a*b) % c = ((a%c) * (b%c)) % c