Big Number and Remainder
Contest: VK Cup 2017 - Wild Card Round 1
Difficulty rating: 2300
Tags: *special, math, number theory

Stepan has a very big positive integer.

Let's consider all cyclic shifts of Stepan's integer (if we look at his integer like at a string) which are also integers (i.e. they do not have leading zeros). Let's call such shifts as good shifts. For example, for the integer 10203 the good shifts are the integer itself 10203 and integers 20310 and 31020.

Stepan wants to know the minimum remainder of the division by the given number m among all good shifts. Your task is to determine the minimum remainder of the division by m.

Input format:
The first line contains the integer which Stepan has. The length of Stepan's integer is between 2 and 200 000 digits, inclusive. It is guaranteed that Stepan's integer does not contain leading zeros.

The second line contains the integer m (2 ≤ m ≤ 108) — the number by which Stepan divides good shifts of his integer.

Output format:
Print the minimum remainder which Stepan can get if he divides all good shifts of his integer by the given number m.

Constraints:
Time limit: 3.0 s
Memory limit: 256.0 MB

Note:
In the first example all good shifts of the integer 521 (good shifts are equal to 521, 215 and 152) has same remainder 2 when dividing by 3.

In the second example there are only two good shifts: the Stepan's integer itself and the shift by one position to the right. The integer itself is 1001 and the remainder after dividing it by 5 equals 1. The shift by one position to the right equals to 1100 and the remainder after dividing it by 5 equals 0, which is the minimum possible remainder.

Example input:
521
3

Example output:
2

Example input:
1001
5

Example output:
0

Editorial:
Представим число Степана как строку s и перевернем её, то есть цифры в строке теперь идут от младших к старшим.
Насчитаем массив pow, где powi равно 10i mod m. Это можно сделать линейно. Будем увеличивать степень, тогда powi = (powi - 1·10) mod m. С помощью это массива насчитаем rem — остаток от деления данного числа на m. Для этого проитерируемся по числу от младших разрядов к старшим, умножим текущую цифру на соответствующую степень, возьмем получившееся число по модулю m, прибавим к rem и возьмем rem по модулю m.
После этого пойем по строке s справа налево, будем сдвигать число на один влево и пересчитывать rem. Пусть n равно количеству цифр в строке s. Тогда, если мы находимся в позиции i, нужно вычесть из rem число si·pown - 1 и взять rem по модулю m. После этого rem может стать отрицательным. В таком случае, прибавим m к rem. После этого нужно умножить rem на 10, так как все цифры кроме si теперь входят в число с степенью на единицу больше, чем было до этого. Теперь вновь возьмем rem по модулю m. После этого нужно лишь прибавить si·pow0, а так как десять в нулевой степени равно единице, то нужно просто прибавить si, так как после сдвига она становится младшим разрядом сдвинутого числа. После этого нужно вновь взять rem по модулю m.
Таким образом, мы корректно пересчитали остаток. Если цифра, стоящая перед si не равна нулю, то есть в результате сдвига на один влево мы получаем корректное число, нужно обновить ответ значением переменной rem.