vb.net - 确定十进制扩展中的最长重复循环

Question

今天遇到this article about decimal expansion我立即受到启发，在 Project Euler Problem 26 上修改我的解决方案包括这种新的数学知识以获得更有效的解决方案(无暴力破解)。简而言之，问题是找到 1-1000 范围内的 d 值，这将使表达式“1/d”中的重复周期的长度最大化。

在没有对问题做任何进一步提高解决问题效率的假设的情况下，我决定坚持

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

这允许我为 D 的任何值找到最长的重复周期 (t) 和周期的起点 (s)。

问题在于等式的 eksponential 部分，因为这会在使用模数减少它们之前生成非常大的值。没有整数值可以处理这么大的值， float 据类型似乎计算错误。

我目前正在使用此代码:

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 循环，然后在您进行时通过使用条件检查计算的数字是否大于模数来获取数字的模数。这有助于使数字更小并保持在您的模数范围内。