Матч 390, Конкатенация числа (ConcatenateNumber)

Дивизион 2, Уровень 2; Дивизион 1, Уровень 1

Задано натуральное число number. Необходимо найти наименьшее количество копий number, объединение которых дает число, делящееся на k. Если искомого объединения копий number не существует, вернуть -1.

Класс: ConcatenateNumber

Метод: int getSmallest(int number, int k)

Ограничения: 1 £ number £ 10⁹, 1 £ k £ 10⁵.

Вход. Целые числа number и k.

Выход. Наименьшее количество копий number, объедининение которых дает число, делящееся на k. Если искомого объединения копий number не существует, вернуть -1.

Пример входа

number	k
2	9
121	11
35	98765

Пример выхода

9

1

9876

РЕШЕНИЕ

математика

Обозначим через d_i остаток от деления числа, полученного конкатенацией i копий числа number, на k. Тогда d₀ = number mod k, d_i+1 = (d_i * 10^tens + number) mod k (tens – количество цифр числа number). Наименьшее i, для которого d_i = 0, будет ответом. Если требуемое i существует, то i £ k. Если среди i £ k ни одно из значений d_i не равно 0, то искомой конкатенации копий числа number не существует, возвращаем -1.

Во избежание переполнения вычисления следует проводить в 64 целочисленном типе данных long long.

ПРОГРАММА

#include <stdio.h>

class ConcatenateNumber

{

public:

int getSmallest(int number, int k)

{

int i;

long long n, tens = 1;

while(tens <= number) tens *= 10;

n = number %= k;

for(i = 1; i <= k; i++)

{

if (!n) return i;

n = (n * tens + number) % k;

}

return -1;

}

};