Объяснение алгоритма поиска числа m, состоящего из цифр 0 и 1, которое делится на число n

Question

Вот фрагмент кода из курса udemy, который я сейчас изучаю, в котором используется принцип голубиная дыра , чтобы найти число, состоящее из нулей и единиц, делимых на число n.

void findNumber(int n) {
int cur_rem = 0;
for(int i = 1; i <= n; i++) {
    cur_rem = (cur_rem * 10 + 1) % n;
    if(cur_rem == 0) {
        for(int j = 1; j <= i; j++)
            cout << 1;
        return;
    }
    if(fr[cur_rem] != 0) {
        for(int j = 1; j <= i - fr[cur_rem]; j++)
            cout << 1;
        for(int j = 1; j <= fr[cur_rem]; j++)
            cout << 0;
        return;
    }
    fr[cur_rem] = i;
}

} Итак, в этом коде мы сначала берем числа 1,11,111, ..., 111..1 (n раз) и смотрим, делятся ли они на данное целое число n. Если они не делятся, мы находим 2 числа в пределах 1,11,111, ... 111..1 (n раз) с одинаковым остатком при делении на число n и вычитаем их, чтобы получить число, которое делится на n. Итак, я понимаю теоретическую часть, но я не понял ни одной строчки кода.

Кто-нибудь, пожалуйста, объясните мне эту строку кода: cur_rem = (cur_rem * 10 + 1) % n; как мы можем получить остаток от текущего числа, умножив остаток от предыдущего числа на 10, а затем прибавление 1 и затем нахождение мода путем деления суммы на заданное целое число n?

Answer 1

Предположим, что последнее число 111 ... (назовем его m), имело остаток r.

m % n = r
m = kn + r

Теперь следующее число 111 ..., назовем его m ', равно единице. di git длиннее м.

m' = 10 m + 1
m' % n = (10 m        + 1) % n
       = (10(kn + r)  + 1) % n
       = (10 kn + 10r + 1) % n
       = (        10r + 1) % n