@outoftime

Armavia, eaa, 1 ≤ N ≤ 6, т.е. надо уметь делать проверку на делимость 2, 4, 6, 8, 10, 12

Делимость на 2: Число делится на 2 тогда и только тогда, когда его последняя цифра делится на 2, то есть является чётной.
Делимость на 3: Число делится на 3, когда сумма его цифр делится на 3.
Делимость на 4: Число делится на 4, когда две последние цифры нули или составляют число, делящееся на 4.
Делимость на 6: Число делится на 6 тогда и только тогда, когда оно делится и на 2, и на 3 (то есть если оно четное и сумма его цифр делится на 3).
Делимость на 8: Число делится на 8, когда три последние цифры составляют число, делящееся на 8. Трёхзначное число делится на 8 тогда и только тогда, когда цифра в разряде единиц, сложенная с удвоенной цифрой в разряде десятков и учетверённой цифрой в разряде сотен, делится на 8.
Делимость на 10: Число делится на 10 тогда и только тогда, когда оно оканчивается на ноль.
Делимость на 12: 12 это 4*3, т.е. надо чтобы соблюдались признаки делимости на 4 и на 3.

Остаётся сложность с 1 ≤ M ≤ 10^18

И тут у меня открылись глаза. У нас есть некое число N и ряд чисел до M, нам надо сказать сколько из них делится на N.

Допустим N это 2, тогда каждое 2е число будет делиться на N, т.е. M/2 чисел мы получим в итоге.
Допустим N это 4, тогда каждое 4е число будет делиться на N, т.е. M/4 чисел мы получим в итоге.
Допустим N это 6, тогда каждое 6е число будет делиться на N, т.е. M/6 чисел мы получим в итоге.
...
В общем случае, получается что последовательность чисел до условно бесконечного M будет иметь M/N чисел делимых на N.

И тут я понял что нам то надо не просто делимость i-ого числа к 2n узнать, но числа которое будет склейкой всех чисел от 1 до i.

С делимостью на 2, 4, 8, 10 нам надо знать максимум 3 последних цифры чтобы сказать ответ формулой при росте i от 1000 (чтобы были эти 3 цифры).

Остаётся вопрос с делимостью на 6, 12 (так как нужна делимость на 3) и что делать для i до 1000.

Итоговое число будет склейкой от 1 до i, у нас получается последовательность 1, 12, 123, 1234, ...

И на этом моменте у меня огромное желание посмотреть как ведёт себя последовательность склеек до большого i (чтобы комп мог вычислить) по модулю 3. Есть ли там цикл и повторяется ли он всё время? Более того, туже операцию охота провести для делимости на 4 и 8, так можно решить проблему малых i одним махом.

Добавлено через 40 секунд
Личка открыта

Добавлено через 5 минут
Делимость точно на 2N надо проверять или на 2^N?

Вернуться к обсуждению:
Задача не проходит по времени, слишком долго выполняется Python

0