Как рассчитать наименьшее число, состоящее только из цифры 1?

Мне дано число k в диапазоне от 1 до 10000. Задача состоит в том, чтобы найти наименьшее кратное, которое может быть записано только с цифрой 1 (известной как repunit). Таким образом, при k = 3 решение равно 111, потому что 3 делит 111, но 3 не делит 1 или 11. При k = 7 решение равно 111111 (шесть единиц).

Как вычислить решение для любого k?

Я понимаю, что мне нужно использовать остатки, так как решение может быть очень большим (или я предполагаю использовать класс BigInteger)

Ответ 1

Если вам всегда гарантировано решение (по крайней мере, для n и кратных 5, нет решения. Я не думал об этом другим, но я думаю, что остальное всегда должно иметь решение):

(a + b) % c = ((a % c) + (b % c)) % c
(a * b) % c = ((a % c) * (b % c)) % c

Где % - оператор по модулю: a % b = the remainder of the division of a by b. Это означает, что мы можем принимать модули между дополнениями и умножениями, которые помогут решить эту проблему.

Используя это, вы можете использовать следующий алгоритм, который является линейным по числу цифр результата и использует память O(1):

number_of_ones = 1
remainder = 1 % n
while remainder != 0:
  ++number_of_ones

  # here we add another 1 to the result,
  # but we only store the result value mod n.
  # When this is 0, that is our solution.
  remainder = (remainder * 10 + 1) % n

print 1 number_of_ones times

Следующий вопрос:, если вы можете использовать 0 и 1?

Ответ 2

Эта проблема включает в себя немного математики, поэтому начнем с нее.

1111... 1 (n цифры 1) =

Обозначим случайное число с k. Поскольку наше условие

следует, что

или

где обозначает оператор конгруэнтности. Мы ищем наименьший такой n, который представляет собой мультипликативный порядок. Мультипликативный порядок существует тогда и только тогда, когда 10 и 9k являются взаимно простыми, что легко проверить. Один пример эффективного вычисления мультипликативного порядка можно найти здесь, и если вам не нужна оптимизированная версия, тогда базовое модульное возведение в степень будет выполнять хитрость:

int modexp(long mod) // mod = 9*k
{            
    int counter = 1;
    long result = 10;            
    while(result != 1)
    {
        result = (result * 10) % mod;
        counter++;
    }

    return counter;
}

Бонус: гарантируется, что эта функция будет работать не более phi(mod) раз, где phi(mod) Функция-функция Эйлера. Важными свойствами этой функции являются phi(mod) < mod и что мультипликативный порядок делит phi(mod).

Ответ 3

Реализация идеи IVlad:

public static String multiple (int n){
    String result = "No Solution";
    if (n > 3 && n % 2 != 0 && n % 5 != 0){
        StringBuilder sb = new StringBuilder("11");
        int k = 11;
        int remain = 11 % n;
        while (remain != 0){
            remain = (remain*10 + 1)%n;
            sb.append('1');
        }
        result = sb.toString();
    }
    return result;
}

public static void main(String[] args) {
    Random rand = new Random();
    for (int i = 0; i < 100; i++) {
        int n = 2 + rand.nextInt(9998);
        System.out.println(n+": "+multiple(n));
    }   
}