Что такое цифровой корень

Некропост

asrinivasan007 → The relationship between IQ and CF Rating

intrusiv → Problem of the Year 2023

nor → [C++] Avoiding temporaries — generalizing i++ using std::exchange

R adewoosh → I’ve completed Project Euler

stdfloat → Unexpected Full Score on oj.uz

Theo830 → Codeforces Round #912 (Div. 2)

xX_I_Have_Esbat_Xx → Reaching my birthyear!

zwezdinv → Codeforces Round #909 (Div. 3)

lanhf → CodeTON Round 7 (Div. 1 + Div. 2, Rated, Prizes!) Editorial

18o3 → Indian ICPC 2023-24 Regionals — Qualifier Rounds

n0sk1ll → Editorial for Codeforces Round #910 (Div. 2)

Некропост

MikeMirzayanov → Часто задаваемые вопросы

Duelist1234 → Codeforces visualizer

Некропост

MikeMirzayanov → Изменение правил об использовании стороннего кода в соревнованиях Codeforces

Alpha_Ashwin007 → Invitation to participate in CodeChef Starters 110 (Rated till 5-stars) — 29th November

_MUSAFIR_ → CP Books Collection( U Can Ignore it )

teemu_ryyti → Ошибочное обвинение в плагиаризме

Некропост

Mister_Minus5 → Junior Balkan Olympiad in Informatics

Careless_man → Hi,Can you help to find book that teaches how use c++ in CP.

NemanjaSo2005 → Codeforces Round 911 (Div. 2) Editorial

yefim123 → Не могу решить задачу

Datapas → I’m blue.

kostia244 → [Important] Update Your ACL

hocky → Tier List

mahmoud13 → TLE on Test 6, I don’t know why is this happening

Блог пользователя GShark

Раскрытие тайны цифрового корня.

Автор GShark, 8 лет назад ,

Недавно мне посчастливилось подготовить задачу про цифровой корень на Russian Code Cup. В результате прорешивания, а также комментариев к разбору, я заметил, что, к сожалению, отнюдь не каждый осведомлен о свойствах данной функции. Я просто не мог остаться равнодушным к этой проблеме.

Для начала рассмотрим определение цифрового корня, взятое с англоязычной Википедии с моим переводом:

Цифровой корень натурального числа — это цифра, полученная в результате итеративного процесса суммирования цифр, на каждой итерации которого для подсчета суммы цифр берут результат, полученный на предыдущей итерации. Этот процесс повторяется до тех пор, пока не будет получена одна цифра.
Например цифровой корень 65,536 это 7, потому что 6 + 5 + 5 + 3 + 6 = 25 и 2 + 5 = 7.

Для начала заметим очевидное свойство ( dr(n) — цифровой корень числа n ):

dr(n) = n, n ≤ 9

Дальше докажем следующий факт: Сумма цифр числа n имеет такой же остаток при делении на 9, как и число n .

В доказательстве нам понадобится формула , докажем ее по индукции:
База:
Переход: .
Нужно доказать . Просто распишем
Таким образом мы доказали по индукции, что .

Вернемся к основному доказательству. Пусть , тогда: n = a_k·10 k + a_{k — 1}·10 k — 1 + . a₁·10 + a₀ . По только что доказанной формуле: следовательно . Что и требовалось доказать.

Теперь по только что доказанному утверждению понятно, что остаток при делении на 9 — инвариант относительно взятия цифрового корня, а поскольку сумма цифр числа меньше самого числа, если число больше 9, справедливы следующие две формулы:

Эти две формулы можно собрать объединить формулой:

Из этой формулы, например, следует периодичность цифрового корня.

Любая задача про цифровой корень становится легче при знании этого несложного факта, надеюсь, что кому-нибудь этот пост покажется полезным.

Поддержано грантом для одаренной молодежи А. А. Шалыто.

Русский [ править ]

Устойчивое сочетание (термин). Используется в качестве именной группы.

Произношение [ править ]

МФА: [ t͡sɨfrɐˈvoɪ̯ ˈkorʲɪnʲ ]

Семантические свойства [ править ]

Значение [ править ]

матем.число, получаемое в результате суммирования цифр какого-либо числа и повторных применений этой операции до тех пор, пока оставшееся значение не будет числом, состоящим из одной цифры ◆ Отсутствует пример употребления (см. рекомендации ).

Цифровой корень

Цифровым корнем (digital root) числа n называется следующее число: берётся сумма цифр числа n , затем сумма цифр у получившегося числа и так далее, пока не получится однозначное число.

Ваша задача — отсортировать данный массив по возрастанию цифровых корней его элементов. Если цифровые корни двух чисел равны, то раньше должно идти меньшее число.

Входные данные

В одной строке заданы элементы массива. Длина массива не превосходит 200 , каждое число положительно и не превышает 10^9 .

Выходные данные

Вывести массив, отсортированный в порядке возрастания цифрового корня.

Пример

Входные данные #1 content_copy

15 14 13 12 11 10 9 8 7

Выходные данные #1 content_copy

10 11 12 13 14 15 7 8 9