Добрый вечер, мальчики и девочки.
Решая на Тимусе задачу 1104, я заметил, что число в k-й системе счисления делится на (k — 1) тогда и только тогда, когда сумма цифр этого числа делится на (k — 1). И этого оказалось достаточно для получения AC по задаче.
Может ли кто-то, пожалуйста, предоставить математическое обоснования данного любопытного факта. Либо предоставить контрпример для его опровержения.
Не понимаю, как получен последний переход, можно подробнее, пожалуйста?
Как думаешь, какой остаток даст число (x + 1)n при делении на x?
А y(x + 1)n при делении на x?
Замени a = k - 1 и b = 1:
(k — 1 + 1) ^ i дает остаток 1 при делении на (k — 1);
(k — 1 + 1) ^ i == ((k — 1) + 1) * ((k — 1) + 1) * ... * ((k — 1) + 1)(i раз). и надо взять отаток при делении на (k — 1) от произведения скобок. если раскроем скобки то в каждом слагаемом будет (k — 1) хотя бы в 1-ой степени, значит оно делится нацело на (k — 1). и будет 1 слагаемое (1 * 1 * .. * 1), к-ое дает остаток 1.