Здравствуйте, Кодт, Вы писали:
К>У меня получается, что делитель разлагается на (20, 9, 11, 13, 13, 19, 37, 47, 61, 401, 1512947) К>Первый множитель не даёт вклад в период, а остальные — дают периоды 1, 2, 6, 6, 18, 3, 46, 60, 200, и какой-то бешеный крендельон. К>(запустил считалку на питоне, и к сожалению, она не торопится... и ещё не досчитала...)
К>Но уже из этого видно, что итоговый период должен быть кратен 1000. К>Или я чего-то путаю?
1) надо одинаковые простые сомножители объединять в группы:
9, 11, 13*13, 19, 37, 47, 61, 401, 1512947
Они дают длины периодов
1, 2, 78, 18, 3, 46, 60, 200, 756473
2) эти длины надо не перемножать, в вычислять НОК. Поэтому наличие 60 и 200 в списке периодов говорит о том, что итоговое число делится на НОК(60,200), т.е. на 600 (не обязательно на 1000)
Здравствуйте, Буравчик, Вы писали:
Б>Ответ: 407133768600. Верно?
Как посчитал?
У меня получается, что делитель разлагается на (20, 9, 11, 13, 13, 19, 37, 47, 61, 401, 1512947)
Первый множитель не даёт вклад в период, а остальные — дают периоды 1, 2, 6, 6, 18, 3, 46, 60, 200, и какой-то бешеный крендельон.
(запустил считалку на питоне, и к сожалению, она не торопится... и ещё не досчитала...)
Но уже из этого видно, что итоговый период должен быть кратен 1000.
Или я чего-то путаю?
Здравствуйте, Кодт, Вы писали:
К>(запустил считалку на питоне, и к сожалению, она не торопится... и ещё не досчитала...)
Считалка длины периода дроби 1/p
Сначала из множителей удаляются двойки и пятерки, т.к. они не влияют на период. Затем на каждом шаге к числу "дописывается" ноль и вычисляется остаток от деления на p. Как только остаток станет равен единицы, период закончился (ведь в начале вычислений остаток тоже был равен единице).
decPeriod p | p `mod` 2 == 0 = decPeriod (p `div` 2)
| p `mod` 5 == 0 = decPeriod (p `div` 5)
| p <= 1 = 0
| otherwise = (fromJust $ elemIndex 1 $ tail $ iterate nextMod 1) + 1
where nextMod m = m * 10 `mod` p
То же самое на Python
def dec_period(p):
while p % 2 == 0:
p /= 2
while p % 5 == 0:
p /= 5
if p <= 1:
return 0
m = 1*10 % p
period = 1
while m > 1:
m = m*10 % p
period += 1
return period
Если p простое больше двух, то 10^(p-1) = 1 (mod p)
А значит искомое m является множителем числа (p-1)
Для нашего примера:
p = 1512947
p-1 = 1512947-1 = 1512946 = 2 * 149 * 5077
Т.е. для поиска m надо проверить следующие степени десятки: 2
149
5077
2*149 = 298
2*5077 = 10154
149*5077 = 756473 <- и вот оно, искомое m
Т.е. для поиска периода достаточно было проверить всего 6 степеней вместо 756473
Правда нужно добавить разложение (p-1) на простые множители, поиск всех степеней (6 штук) и само вычисление степеней
Здравствуйте, Буравчик, Вы писали:
Б>Здравствуйте, Кодт, Вы писали:
К>>У меня получается, что делитель разлагается на (20, 9, 11, 13, 13, 19, 37, 47, 61, 401, 1512947) К>>Первый множитель не даёт вклад в период, а остальные — дают периоды 1, 2, 6, 6, 18, 3, 46, 60, 200, и какой-то бешеный крендельон. К>>(запустил считалку на питоне, и к сожалению, она не торопится... и ещё не досчитала...)
К>>Но уже из этого видно, что итоговый период должен быть кратен 1000. К>>Или я чего-то путаю?
Б>См. последний абзац в раздела Reciprocals of composite integers coprime to 10
Б>1) надо одинаковые простые сомножители объединять в группы: Б>9, 11, 13*13, 19, 37, 47, 61, 401, 1512947
Б>Они дают длины периодов Б>1, 2, 78, 18, 3, 46, 60, 200, 756473
Б>2) эти длины надо не перемножать, в вычислять НОК. Поэтому наличие 60 и 200 в списке периодов говорит о том, что итоговое число делится на НОК(60,200), т.е. на 600 (не обязательно на 1000)
Б>НОК от всех периодов будет равен 407133768600
Здравствуйте, Буравчик, Вы писали:
Б>>>10^m = 1 (mod p) Б>Правда, в нашем случае стоит более узкая задача (=1), и, возможно, существуют еще более быстрые алгоритмы.
Перекуём баги на фичи!
