Метод маленькой теоремы Ферма является математически разумным, и просто перемножать снова и снова на 7 мод 10 ^ 6 - самый простой код, но есть другой подход, который вы можете использовать, который эффективен в вычислительном отношении (но требует более сложного кода). Во-первых, обратите внимание, что при умножении на 7 последняя цифра last зависит только от предыдущей цифры last (т. Е. Мы делаем все в моде 10). Мы умножаем многократно на 7, чтобы получить
7 (4)9 (6)3 (2)1 (0)7 ...
Хорошо, отлично, поэтому, если мы хотим 3, мы начинаем с 7 ^ 3 и поднимаемся оттуда каждые 7 ^ 4. Теперь отметим, что при умножении на 7 ^ 4 последние две цифры зависят только от последних двух цифр 7 ^ 4 и двух последних цифр предыдущего ответа. 7 ^ 4 - это 2401. Таким образом, на самом деле последние две цифры всегда будут одинаковыми при увеличении на 7 ^ 4.
А как насчет последних трех? Ну, 7 ^ 3 = 343 и 7 ^ 4 заканчиваются 401, поэтому мод 1000 мы получаем
343 543 743 943 143 343
У нас есть первые три цифры в столбце № 2 (543), и мы видим, что последовательность повторяется всегда 5, поэтому мы должны подняться на 7 ^ 20.
Мы можем разыгрывать этот трюк снова и снова: узнайте, как часто повторяется следующий блок цифр, найдите правильную подпоследовательность в этом блоке, а затем умножьте не на 7, а на 7 ^ n.
Что мы действительно делаем, так это находим (мультипликативное) кольцо над m-й цифрой, а затем умножаем размеры всех колец вместе, чтобы получить промежуток между последовательными степенями, которые имеют одинаковые N цифр, если мы будем следовать этому метод. Вот некоторый код Scala (2.8.0 Beta1), который делает именно это:
def powRing(bigmod: BigInt, checkmod: BigInt, mul: BigInt) = {
val powers = Stream.iterate(1:BigInt)(i => (i*mul)%bigmod)
powers.take( 2+powers.tail.indexWhere(_ % checkmod == 1) ).toList
}
def ringSeq(digits: Int, mod: BigInt, mul: BigInt): List[(BigInt,List[BigInt])] = {
if (digits<=1) List( (10:BigInt , powRing(mod,10,mul)) )
else {
val prevSeq = ringSeq(digits-1, mod, mul)
val prevRing = prevSeq.head
val nextRing = powRing(mod,prevRing._1*10,prevRing._2.last)
(prevRing._1*10 , nextRing) :: prevSeq
}
}
def interval(digits: Int, mul: Int) = {
val ring = ringSeq(digits, List.fill(digits)(10:BigInt).reduceLeft(_*_), mul)
(1L /: ring)((p,r) => p * (r._2.length-1))
}
Итак, если мы нашли один случай нужных нам цифр, теперь мы можем найти их все, найдя размер соответствующего кольца. В нашем случае, с 6 цифрами (т.е. мод 10 ^ 6) и основанием 7, мы находим повторяющийся размер:
scala> interval(6,7)
res0: Long = 5000
Итак, мы получили наш ответ! 7 ^ 7 - первое, 7 ^ 5007 - второе, 7 ^ 10007 - третье и т. Д.
Так как это общее, мы можем попробовать другие ответы ... 11 ^ 11 = 285311670611 (8-значное число). Давайте посмотрим на интервал:
scala> interval(12,11)
res1: Long = 50000000000
Итак, это говорит нам о том, что 11 ^ 50000000007 является следующим числом после 11 ^ 11 с тем же начальным набором из 12 цифр. Проверьте вручную, если вам интересно!
Давайте также проверим с 3 ^ 3 - какова следующая степень 3, десятичное расширение которого заканчивается на 27?
scala> interval(2,3)
res2: Long = 20
Должно быть 3 ^ 23. Проверка:
scala> List.fill(23)(3L).reduceLeft((l,r) => {println(l*r) ; l*r})
9
27
81
243
729
2187
6561
19683
59049
177147
531441
1594323
4782969
14348907
43046721
129140163
387420489
1162261467
3486784401
10460353203
31381059609
94143178827
Да!
(Переключил код в правках, чтобы использовать BigInt, чтобы он мог обрабатывать произвольные числа цифр. Однако код не выявляет вырожденные случаи, поэтому убедитесь, что вы используете простое число для мощности ....)