Задача не проходит по времени, слишком долго выполняется

Условие:
Серийные номера игр компании «1D Software» являются идущими подряд элементами числовой последовательности A. Десятичная запись i-го элемента этой последовательности строится конкатенацией всех целых положительных чисел, начиная с 1 (номер первого экземпляра игры) и заканчивая i. Например, A2=12, A11=1234567891011.

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

Вам задано количество экземпляров M некоторой игры и число N. Вычислите, сколько экземпляров содержит дополнительные уровни.

Формат ввода
В единственной строке входа заданы два целых числа M и N (1 ≤ M ≤ 10¹⁸, 1 ≤ N ≤ 6).

Формат вывода
Выведите одно целое число — количество экземпляров игры, содержащих дополнительные уровни

Пример 1
Ввод
1 1
Вывод
0

Пример 2
Ввод
10 1
Вывод
5

Пример 3
Ввод
10 2
Вывод
2

Пример 4
Ввод
10 3
Вывод
1

Пример 5
Ввод
10 4
Вывод
1

Пример 6
Ввод
10 5
Вывод
1

Пример 7
Ввод
10 6
Вывод
1

Рабочий код, но превышающий лимит времени

0

Сообщение от Armavia но превышающий лимит времени

и с чем это может быть связано?

Добавлено через 1 минуту

Сообщение от Armavia 1018

1018 цифр так то не много.

0

Опечатка, это 10¹⁸

0

а это много)) Что делать?

0

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 секунд

Сообщение от Armavia Модераторы удаляют

Личка открыта

Добавлено через 5 минут

Сообщение от Armavia 2 ** int(c[1])

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

0

Ограничение времени 1 секунда
Ограничение памяти 256Mb

Серийные номера игр компании «1D Software» являются идущими подряд элементами числовой последовательности . Десятичная запись -го элемента этой последовательности строится конкатенацией всех целых положительных чисел, начиная с 1 (номер первого экземпляра игры) и заканчивая . Например, ,.

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

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

Формат ввода
В единственной строке входа заданы два целых числа и (1 ≤ M ≤ , 1 ≤ N ≤ 6).

Пример 1
Ввод Вывод
1 1
0
Пример 2
Ввод Вывод
10 1
5
Пример 3
Ввод Вывод
10 2
2
Пример 4
Ввод Вывод
10 3
1
Пример 5
Ввод Вывод
10 4
1
Пример 6
Ввод Вывод
10 5
1
Пример 7
Ввод Вывод
10 6
1

Добавлено через 10 минут
Делимость на 2^N, вроде как, надо в двоичной системе смотреть. Но число мы строим в 10-чной приклеивая новые цифры сзади и как подойти к изменениям 2-чной записи я, пока, ума не приложу.

0

outoftime, а мне это зачем? я знаю как решать эту задачу. Да и ТС разъяснять это нет смысла, судя по уроню.
вообще это какая то олимпиада как я понял.

0