Здраствуте уважаемые юзеры!
Недавно прочитав разбор задачи 131 раунда(div 2) — B.Домашняя задача.
Пришло мысл про то:
- А что если будет задачи типа.
Дается чило N (кол-во цифр в N 10^5) и X.
Далее можно делать эти операций:
1) Менять местами некоторые цифры
2) Удалять некоторые цифры
Нужно вывести максимальное число N которое прошёл через выше описанные операций и делится на число X.
Недавно копался в Wiki и нашёл эту статью.
Придумал решение на некоторые случаи:
Если X = 2: Число делится на 2 тогда и только тогда, когда его последняя цифра делится на 2, то есть является чётной. Решение: Можно понять посмотрев на код. Div_to_2.cpp
Если X = 3: Число делится на 3 тогда и только тогда, когда сумма его цифр делится на 3. Решение: Возьмем все цифры в невозрастающем порядке, если сумма цифр кратна 3, то это и есть ответ. Если остаток от деления вышел 1, то нужно убрать 1 цифру у которой остаток от деления на 3 равен 1. Если такой не нашли то нужно убрать 2 цифры с остатком 2. Аналогично рассматривается случай когда изначальный остаток равен 2. Так-же нужно рассмотреть случай когда остались только нули, в этом случае нужно вывести только 1 ноль. Div_to_3.cpp
Если X = 4: Число делится на 4 тогда и только тогда, когда две его последние цифры составляют число, которое делится на 4. Решение: Можно понять посмотрев на код. Div_to_4.cpp
Если X = 5: Число делится на 5 тогда и только тогда, когда последняя цифра делится на 5, т. е. если она 0 или 5. Решение: Можно понять посмотрев на код. Div_to_5.cpp
Если X = 6: Число делится на 6 тогда и только тогда, когда оно делится и на 2, и на 3 (то есть первым делом получаем максимальное число которое делится на[мы уже это умеем]. Далее получаем число которое делится на 2[мы это тоже умеем]). Решение: Можно понять посмотрев на код. Div_to_6.cpp
Напишите пожалуйста разбор на более сложные случаи 7,8,11,13,14,17.
Для 8 — нужно что-бы последние 3 цифры образовали число кратное 8и. То есть там нужно перебрать цифры которые будем ставить в конец, смотреть что-бы начало было как можно больше и из тех цифр, что имеем в конце можно было составить число кратное 8и.
С шестёркой не так всё просто — может получиться, что из максимального числа, которое делится на 3, мы не получим число, делящееся на 2. Пример — 999475, правильный ответ — 99954.
По поводу восьмёрки и других степеней двойки всё просто — число делится на 2^k, если k его последних цифр составляют число, делящееся на 2^k. Аналогично с 5^k.
С 11 сложнее. Число делится на 11, если разность суммы цифр на чётных местах и суммы цифр на нечётных делится на 11. Поэтому необходимо найти такое разбиение из подмножества данных цифр, а затем выписать их в порядке убывания.
Насчёт остальных чисел ничего умнее простой проверки на делимость, кажется, не придумали.
"Насчёт остальных чисел ничего умнее простой проверки на делимость, кажется, не придумали."
просто ты их не знаешь. признаков делимисти на всякие разные числа очень много, и некоторые обобщаются на другие системы счисления. признак делимости на 9 например здесь не упоминается (по крайней мере я не заметил)
Ну, признаков, безусловно, очень много. Вопрос в том, как их использовать в олимпиадном программировании. Взять тот же признак делимости на 7 из упомянутой статьи — предлагается по сути просто пройти по числу слева направа, вычисляя его префиксы по модулю 7.
Про делимость на 9 — признак действительно простой для использования. Но вот как использовать признаки делимости на всякие двузначные простые (типа 19, 59 и т.д.) мне не очень понятно.
Вообще говоря для всех чисел, взаимнопростых с 10, существует признак делимости вида "возьмем группы по k цифр, сложим их и делится только тогда, когда и исходное число делится", правда это не всегда очень полезно в силу того, что K может быть большим. Но если делимое сильно больше делителя — вполне.
(Кстати отсюда же и второй признак для 11и) — Складывать группы по 2 цифры.
Лучше не страдайте фигней, а решайте D-шку :).
P.S. Хотя кот бы говорил: я сейчас сам вместо решения чего-либо нормального решаю сокобан с Тимуса...
Для семерки есть такой признак (он выводится из всяких преобразований по модулю 7):
Пусть есть число 10n - 1an - 1 + 10n - 2an - 2 + ... + 10a1 + a0, которое надо проверить (ai — его цифры),
и массив b = {2, - 1, - 3, - 2, 1, 3} (циклический, а эти 6 чисел — период).
Теперь, число делится на 7 тогда и только тогда, когда выражение bn - 1an - 1 + bn - 2an - 2 + ... + b1a1 + b0a0 делится на 7.
Может, это поможет?
P.S. Я просто не могу не запостить это: http://otvet.mail.ru/answer/62444614/
Отличный ответ по ссылке в PS :)
это признак Паскаля. Подходит для всех натуральных чисел, не только для 7
http://blog.tanyakhovanova.com/?p=159
А дальше какое-то ДП по автомату и взятым цифрам? Если получится, этот способ подойдёт для всех делителей.
если написать формулы вместо графа, то этот метод выглядит так:
пусть дано число
и мы хотим найти остаток от его деления на m. Вычисляем
Ответом будет rn
Остаток искать неинтересно, это по тому автомату сходу делается. Можно ли как-то с помощью этого решить исходную задачу?