ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила
вернуться в форум

Обсуждение задачи 1104. Не спрашивай даму о возрасте

Чёрт знает почему это так
Послано Mahilewets 20 июл 2017 00:29
Ну я вспомнил что число в десятичной системе счисления
Делится на 9 (то есть на 10-1)
Если сумма его цифр делится на 9
Я предположил что в любой k-ичной системе счисления верно
Что если сумма цифр некоторого числа делится на k-1 то и это число делится на k-1
И это оказалось правдой для тех k
Которые содержатся в тестах к этой задаче.
Re: Чёрт знает почему это так
Послано ViktYusk 17 ноя 2018 13:42
Большое спасибо! Эта подсказка мне помогла.
Re: Чёрт знает почему это так
Послано Alikhan Zimanov 22 май 2020 21:26
Доказательство вашего утверждения:
Пусть мы сейчас в k-ой системе счисления и если прочитать наше число X слева направо, то получим цифры a_n, a_{n - 1}, ... , a_1, a_0 (при этом 0 <= a_i <= k - 1 для всех i). Тогда в десятичной системе счисления оно будет равно X = a_n * k ^ n + a_{n - 1} * k ^ {n - 1} + ... + a_1 * k + a_0. Так как k = 1 (mod (k - 1)), то X = a_n + a_{n - 1} + ... + a_1 + a_0 (mod (k - 1)). Значит, X делится на (k - 1) тогда и только тогда, когда его сумма цифр делится на (k - 1).