确定十进制扩展中的最长重复周期

Question

今天我遇到了关于十进制扩展的这篇文章,我立刻受到启发,重新设计了我在Project Euler Problem 26上的解决方案,将这个新的数学知识包含在一个更有效的解决方案中(没有强制执行).简而言之,问题是找到d范围为1-1000的值,其将使表达式"1/d"中的重复循环的长度最大化.

如果不对问题做出任何进一步的假设,可以进一步提高解决问题的有效性,我决定坚持下去

10^s=10^(s+t) (mod n)

这允许我在D的任何值中找到最长的重复周期(t)和周期的起始点.

问题在于等式的指数部分,因为这将在通过使用模数减小之前产生极大的值.没有整数值可以处理这个大值,并且浮点数据类型看起来计算错误.

我目前正在使用此代码:

Private Function solveDiscreteLogarithm(ByVal D As Integer) As Integer
Dim NumberToIndex As New Dictionary(Of Long, Long)()
Dim maxCheck As Integer = 1000

For index As Integer = 1 To maxCheck
   If (Not NumberToIndex.ContainsKey((10 ^ index) Mod D)) Then
        NumberToIndex.Add((10 ^ index) Mod D, index)
   Else
        Return index - NumberToIndex((10 ^ index) Mod D)
   End If
Next

Return -1
End Function

在某些时候将计算"(10 ^ 47)mod 983"导致783,这不是正确的结果.正确的结果应该是732.我假设它是因为我使用的是整数数据类型并且它导致溢出.我尝试使用double代替,但这给了更奇怪的结果.

那么我的选择是什么？

Answer 1

我没有使用^来做你的力量,而是使用乘法做一个for循环,然后通过使用条件检查计算出的数量是否大于mod来获取数字的mod.这有助于使数字更小并且在您的mod编号的范围内.