e-olymp 50. Разрезанное число

Задача

Василий на бумажке в виде полоски написал число, кратное $d$. Его младший брат Дмитрий разрезал число на $k$ частей. Василий решил восстановить написанное число, но столкнулся с проблемой. Он помнил только число $d$, а чисел, кратных $d$, можно сложить несколько.
Сколько чисел, кратных числу $d$, может составить Василий, если составляя исходное число, он использует все части.

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

В первой строке записано два числа $d$ и $k$ $\left(1 ≤ k < 9, 1 ≤ d ≤ 100\right)$. В следующих $k$ строках находятся части числа. Количество цифр в разрезанных частях не превышает $10.$

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

Количество разных чисел.

Тесты

Входные данные Выходные данные
$5$ $3$
$13$
$85$
$45$
$4$
$11$ $2$
$1$
$111$
$1$
$11$ $3$
$11$
$8$
$11$
$0$
$71$ $8$
$4018916609$
$7495223237$
$3405637482$
$3166003637$
$8998228133$
$1141886496$
$9124347310$
$7736090711$
$584$

Код программы

Решение задачи

Согласно свойствам остатков от деления, остаток от деления суммы двух натуральных чисел на натуральное число $d$ совпадает с остатком от деления на $d$, который при делении на $d$ дает сумма их остатков. А также остаток от деления произведения двух натуральных чисел на натуральное число $d$ совпадает с остатком от деления на $d$, который при делении на $d$ дает произведение их остатков.
Значит, мы можем решить обычным перебором, но на каждом действии берем остаток от деления на $d$.
Также части чисел могут совпадать, в связи с чем необходима проверка на то, что мы составленное число еще не записывали. Для этого мы будем хешировать полученное число следующим образом: последнюю цифру умножим на $101^0$, предпоследнюю — на $101^1$ и так далее.
Если наш конечный результат делится на $d$ без остатка и если составленное число встречается в первый раз, то увеличиваем счетчик на $1$.

Ссылки

Условие задачи на e-olymp
Код решения

Related Images:

e-olymp 109. Нумерация

Задача взята с сайта e-olymp.com.

Условие 

Для нумерации [latex]M[/latex] страниц книги использовали [latex]N[/latex] цифр. По заданному [latex]N[/latex] вывести [latex]M[/latex] или [latex]0[/latex], если решения не существует. Нумерация начинается с первой страницы.

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

Единственное число [latex]N[/latex]. В книге не более [latex]1001[/latex] страницы.

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

Искомое количество страниц.

Тесты :

N 8 21 22 113 999 1001
M 8 15 0 61 369 0

Код программы

Примечание

Общее (и более компактное) решение можно написать, подключив библиотеку <cmath> и воспользовавшись функцией логарифма с основанием 10.

Код программы (вторая версия)

 

Ссылки 

Засчитанное решение на e-olymp.com .

Рабочий код на Ideone.com .

 

Related Images: