0

试图解决这个问题：

对于正数 n，将 S(n) 定义为整数 x 的和，其中1 < x < n和x^3 ≡ 1 mod n。

当 时n=91，x 有 8 个可能的值，即：9、16、22、29、53、74、79、81。因此，S(91)=9+16+22+29+53+74+79+81=363。

找到 S(13082761331670030)。

当然，我的代码适用于S(91)并且在尝试查找时S(13082761331670030)出现两个不同的错误。

这是我的代码：

 def modcube(n):
     results = []
     for k in range(1,n):
            if k**3%n==1:
             results.append(k)
     return results

这会产生Overflow error: range has too many items.当我尝试使用“xrange”而不是“range”时，我收到一条错误消息，指出 python int 太大而无法转换为 c long。我也刚刚尝试了其他几件事，但没有成功。

谁能指出我正确的方向，而不告诉我确切的解决方法？
请不要剧透。我已经做了两天了，我的下一个选择是尝试在 Java 中实现它，因为我是 Python 新手。

4

2 回答 2

2

我认为您需要在这里了解两个概念：

1. C 和 Python 中的整数表示

您使用的 Python 实现称为 CPython，因为它是使用 C 语言编写的。在 C 中，长整数（通常）是 32 位长。这意味着它可以处理介于 -2147483647 和 2147483648 之间的整数。在 Python 中，当整数超出此范围时，它会将它们转换为任意精度的整数，其中整数的大小仅受计算机内存的限制。但是，对这些任意整数（在 Python 中称为长整数）的操作比对 32 位整数的操作慢一个数量级。

range2.和的区别xrange：

range产生一个列表。如果有range(10)，它会将列表[0, 1, ... 9]完全存储在内存中。这就是为什么在内存中存储一​​个包含 13082761331670030 个项目的列表太过分了。假设每个数字都是 64 位，则需要 93 TB 的 RAM 来存储整个列表！

xrange产生一个迭代器。它一一返回每个数字。这样，它允许对列表的每个数字执行操作，而无需将整个列表存储在内存中。但是同样，对 13082761331670030 不同的数字执行计算可能需要比你想象的更多的时间......另一件事xrange是它不适用于 Python 长整数；它被限制（出于速度原因）为 32 位整数。这就是为什么您的程序无法使用xrange.

底线：欧拉计划问题（或多或少）按难度分类。你应该先从较低的问题开始。

于 2013-03-21T04:25:06.390 回答
1

你想要提示，而不是解决方案。

提示：

  1. 考虑 13082761331670030 的素数因子等于以下素数： 2 x 3 x 5 x 7 x 11 x 13 x 17 x 19 x 23 x 29 x 31 x 37 x 41 x 43

  2. 中国剩余定理

  3. 仅仅因为x^3 ≡ 1 mod n并不意味着除了 3 之外没有其他值满足这个条件。具体来说，prime1 ** (prime2 - 2) % prime2

我的 Python 解决方案是 86 毫秒...

于 2013-03-21T05:51:07.903 回答