Проблема. У дроби единицы в числителе 1. Например, - 1 / 2,1 / 3,1 / 4,1 / 5 и т. Д. В их десятичном представлении они -
1/2 = 0.5
1/3 = 0.(3)
1/4 = 0.25
1/5 = 0.2
1/6 = 0.1(6)
1/7 = 0.(142857)
1/8 = 0.125
1/9 = 0.(1)
1/10 = 0.1
Где 0,1 (6) означает 0,1666666… и имеет повторяющийся цикл из 1 цифры. Видно, что 1/7 имеет повторяющийся цикл из 6 цифр. Учитывая целое число N, найдите наименьшее значение d ‹N, такое, что d имеет самый длинный повторяющийся цикл.
Например, если N = 10, на выходе должно быть 7 (1/7 имеет самый длинный повторяющийся цикл).
Это задача 26 от Project Euler. Другой вариант - hackerrank (другой размер ввода).
Математика- Один из способов решения этой проблемы - использование грубой силы (метод длинного деления). Этого могло быть достаточно, чтобы решить проблему проекта Эйлера. Однако этот подход не сработает при большем значении проблемы хакерского ранга. Вот более умное решение.
Если мы запишем первые несколько дробей в десятичной форме, мы сможем выделить три различных типа дробей:
- Завершающие дроби - это дроби, у которых нет повторяющегося цикла. Например, 1/2 = 0,5, 1/4 = 0,25, 1/5 = 0,2 и т. Д.
- Полностью повторяющийся - дроби вида 1/3 = 1. (3), 1/7 = 1. (142857), 1/9 = 1. (1) и т. д. где повторяется вся десятичная часть.
- Повторение после неповторяющейся части - Пример: 1/6, где повторение начинается с десятичной части после нескольких неповторяющихся цифр.
1/6 = .1 (6), где «1» не повторяется.
Случай 1. Прерывание дробей
Завершающие дроби не представляют для нас интереса в этом вопросе, поскольку длина повторяющегося цикла в них всегда будет равна 0. Однако нам нужно определить целые числа, обратные числа которых образуют завершающие дроби. Если 1 / n является завершающим десятичным числом, существует целое число k, такое, что -
10^k*(1/n) -> is an integer
Например,
10² (1/4) = 100 * 0,25 = 25 = ›Здесь k = 2.
10¹ (1/5) = 10 * 0,2 = 2 =› Здесь k = 1 .
Из этого следует
=> 10^k mod n = 0
=> n is a factor of 10^k.
Это возможно только в том случае, если
n = (2^a*5^b) ; for some a and b
И k будет равно большему из 'a' и 'b'.
Например,
1 / 4 = 1 / 2²
10² / 2² = 25
Здесь k = 2.
If a number can be represented as (2^a)*(5^b), its reciprocal is a terminating decimal.
Случай 2. Полностью повторяющаяся десятичная дробь
Если 1 / n является полностью повторяющимся десятичным числом, существует целое число k такое, что -
10^k*(1/n) has the same decimal part as (1/n)
Например,
1/7 = 0. (142857) ……………………………………… (уравнение 1)
10⁶ (1/7) = 142857. (142857) ) ………………………………. (Уравнение 2)
Здесь k = 6.
Это означает -
10^k*(1/n)-(1/n) -> is an integer
=> (10^k -1)/n -> is an integer
=> (10^k-1) mod n = 0
=> 10^k mod n = 1 ......................(eqn 3)
Например,
вычитая (уравнение 1) из (уравнение 2), мы имеем:
10⁶ (1/7) - (1/7) = 142857
Здесь 10⁶ mod 7 = 1
For a given n, if we find the least value of k, for which (eqn 3) holds true, the length of the repeating decimal cycle for the reciprocal of n is k.
Случай 3. Повторение после неповторяющейся части
Думая о тех же принципах, что и для случаев 1 и 2, нам нужно найти способ представить десятичное число, которое повторяется после неповторяющейся части, как целое число. Пример: 1/6 = .1 (6).
Здесь неповторяющаяся часть имеет длину 1, а повторяющаяся часть также имеет длину 1.
Мы можем умножить 1 / n на определенную степень d, равную 10, так, чтобы неповторяющаяся десятичная часть находилась слева от десятичной точки.
Если 1 / n - десятичное значение, которое повторяется после неповторяющейся десятичной точки. -повторяющаяся часть, существует целое число d такое, что-
10^d*(1/n) -> a completely repeating decimal.
Например,
1/6 = 0,1 (6)
= ›10¹ * (1/6) = 1. (6) …………………………………………… ……… (уравнение 1)
Здесь d = 1
Также существует целое число k такое, что
(10^(d+k))(1/n) has the same decimal part as 10^d(1/n)
Например,
= ›10 ^ (1 + 1) * (1/6) = 10² (1/6) = 16. (6) ……………………………… .. (уравнение 2)
Здесь k = 1
Из этого следует-
10^(d+k)(1/n)-10^d(1/n) -> is an integer
=> (10^(d+k) -10^d)/n -> is an integer
=> 10^d(10^k-1)/n = 0
10^d cancels out with all 2's and 5's from n.
If n = (2^a)*(5^b)*other factors, for some a and b.
n' = n/(2^a)(5^b) [Removing all 2s and 5s]
d = max(a,b) such that 10^d cancels out all multiples of 2 and 5 from n.
Now, we can solve this independently as-
(10^k-1)/n' -> is an integer.
From Case2, this implies that we solve for-
10^k mod n' = 1 .....................................(eqn 3)
Например,
вычитая (уравнение1) из (уравнение2), мы имеем-
10² (1/6) - 10 (1/6) = 15
= ›10 (10–1) / 6 = 15
= ›5 (10–1) / 3 = 15 (Вычитаем из n числа, кратные 2 и 5)
Теперь решаем часть (10–1) / 3 независимо < br /> Из случая 2 это означает, что мы решаем для = ›10 ^ k mod 3 = 1. Здесь k = 1.
После того, как все числа, кратные 2 и 5, будут исключены из n, его можно будет решить, как в случае 2, описанном выше. Другими словами, неповторяющаяся часть десятичного представления вносится в число двоек и пятерок в n. Поскольку нас интересует повторяющийся цикл, мы можем разложить n на множители, удалить все числа, кратные (2 и 5), и решить его, как в случае 2 выше.
For a given n, if we first find n' = n/(2^a*5^b) {for maximum a and b}, and find the least value of k, for which (eqn 3) holds true, the
length of the repeating decimal cycle for the reciprocal of n is k.
Обзор алгоритма -
- Для каждого целого числа n, меньшего, чем входная граница, о которой идет речь, представьте его как сопростое число 10, т. Е. удалите все символы 2 и 5, чтобы представить его в форме n ’= n / (2 ^ a * 5 ^ b) {для макс. a и b}.
- Найдите самый длинный повторяющийся десятичный цикл, решив следующее уравнение для k - n ’^ k mod n’ = 1
- Сохраните значение n, для которого мы нашли самый длинный цикл на данный момент. Это можно использовать как поиск по запросам в Вопросе хакерранга.
