b% a где b очень большое

-2

Нам даны два целых числа: a и b, a <= 100000, b < 10^250. Я хочу рассчитать b% a. Я нашел этот алгоритм, но не могу понять, как он работает.b% a где 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; 
}

Пожалуйста, объясните логику этого. Я знаю основные свойства модульной математики.

Спасибо.

источник

2015-04-07 daft300punk

только магическое число здесь 48. ASCII-код символа «0». Итак '' 0 "- 48 == 0;' и '" 1 "- 48 == 1;' и так далее. Остальная часть кода вам понять. – teivaz

@MarkGraph ваш сарказм лучше, чем ваши предположения. – daft300punk

Кусок кода, который вы «нашли», не принимает «два целых числа, a и b», так что это не очень хорошее начало. –

Это довольно легко понять, если вы знаете модульную арифметику, выражение (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) - это преобразование с символа на цифру.

источник

2015-04-07 10:50:42 Predelnik

Я не понимаю, как было упрощено (... ((b [0] по модулю a) * 10 + b [1]) modulo a) * 10 + ... + b [n]) modulo a – daft300punk

@AbhilashSingh для вычисления коэффициента до 'b [i]' вам нужно будет несколько '10 по модулю a' из точно' n - i «скобка», которая является такой же, как «(10^(n - i)) по модулю a' из первого выражения. – Predelnik

В основном эта функция реализует Horner's Algorithm для вычисления десятичного значения b.

Как объяснено @Predelnik, значение b многочлен, коэффициенты которого являются цифры b и переменная x является 10. Функция вычисляет по модулю на каждой итерации, используя тот факт, что по модулю совместим с сложения и умножения:

(a+b) % c = ((a%c) + (b%c)) % c 
(a*b) % c = ((a%c) * (b%c)) % c

источник

2015-04-07 11:31:12 fjardon

b% a где b очень большое

ответ

Смежные вопросы