Список голосов Thank You

[Sirion]

Обозначим за d количество цифр в числе n, за k - то, что останется от m, если отрезать от него n (и, возможно, ведущие нули), за p - (количество цифр в числе m) вычесть d (это не обязательно равняется числу цифр в числе k, ибо те самые ведущие нули). Тогда:

m = k + n*10^p = (k*10^d + n)*n
k*(10^d*n-1) = n*(10^p-n)
k = n*(10^p-n)/(10^d*n-1)

Заметим, что если по этой формуле получится целое k, то оно заведомо будет меньше 10^p, то есть влезет по цифрам. Осталось понять, всегда ли мы можем получить целое k при заданном n, варьируя p.
Нам нужно, чтобы 10^p - n делилось на 10^d*n - 1. Это будет происходить тогда и только тогда, когда (10^p - n)*10^d + (10^d*n - 1) = 10^p+d - 1 делится на 10^d*n - 1. Заметим, что 10 и 10^d*n - 1 взаимно просты. Значит, по теореме Эйлера 10^{ф(10d*n - 1)} - 1 делится на 10^d*n - 1. Следовательно, для всякого n существует m = k + 10^{ф(10d*n - 1)-d}
= n*(10^{ф(10d*n - 1)-d}-n)/(10^d*n-1) + 10^{ф(10d*n - 1)-d}