在Python中计算更大数的模数

Question

我的代码在处理小数字时可以正常运行，但是当我处理大数字时出现了运行错误。

n = int(input().strip())
a=[]
for a_i in range(n): 
  a,n,m = [int(a_temp) for a_temp in input().strip().split(' ')]

  #n = test cases
  #a is a number 
  # n is no of times a will repeat itself (for example a=12 ,n =2 so y=1212.)
  #m is divisor

  y=[a]*n
  #print(y)

  s = map(str, y)   # ['1','2','3']
  s = ''.join(s)          # '123'
  s = int(s)
  #print(s)

  mod=s%m
  print(mod)

输入：

2  
12 2 17  
523 3 11

输出：

5
6

对于这样的输入：

2
366 457429086499 164868357
764 438211694736 385254849

它会出现错误：

Traceback (most recent call last):
  File "C:/Users/LENOVO/AppData/Local/Programs/Python/Python35-32/try123.py", line 11, in <module>
    y=[a]*n
OverflowError: cannot fit 'int' into an index-sized integer

如何解决这个问题？

- Pygirl

---

请看这个链接：https://dev59.com/-XRB5IYBdhLWcg3wuZQ1 - ppasler

如果[366]*457429086499是可能的，它将有457,429,086,499个条目，并且需要超过1TB的存储空间。你真的想这样做吗？ - John Coleman

对于像这样具有较大数字的测试用例，我必须执行模运算。还有其他方法吗？我的意思是是否有任何其他语法可以在y=[a]*n的位置使用。 - Pygirl

你想做什么？你期望 366 457429086499 164868357 的输出是什么？我无法想象得到那个输出的唯一方法是创建一个非常大的列表。 - John Coleman

输出结果为： 2013258 236245506 - Pygirl

Answer 1

这个问题没有单纯的解决方案适用于大数。你需要使用一些聪明的代数和/或数论。366, 366366, 366366366, ...是等比数列的部分和。有一个标准公式可以对它们进行求和，但不幸的是它涉及除法，而除法与模算术不兼容。这个答案提供了一个聪明的递归解决方案，类似于标准模指数方法。在Python中实现并使用正确的参数调用它会得到：

def geom(a,k,n):
    """calculates (1 + a + a^2 + ... + a^(k-1)) mod n)"""
    if k <= 2:
        return sum(a**i for i in range(k)) % n
    else:
        m = k//2
        b = pow(a,2,n)
        g = ((1+a)*geom(b,m,n))%n
        return g if k%2 == 0 else (g + pow(a,k-1,n))%n

def f(a,m,n):
    """ returns aaaa...a (m times) modulo n"""
    k = len(str(a))
    r = pow(10,k,n)
    return (a*geom(r,m,n))%n

For example,

>>> f(366, 457429086499,164868357)
2013258

这个计算几乎是即时完成的。

- John Coleman

---

但是我们不能在Python中使用任何内置函数来处理更大的数字吗？ 我尝试使用type方法，但它不起作用。 - Pygirl

一个可能有用的观察是，例如 366366366 = 366 *（1001001）。如果您可以找到类似于 1001001％n 的数字模式（以1开头和结尾，中间穿插着相等长度的0块），那就足够了。 - John Coleman

@KritiSahu 我不太确定你所说的“我尝试使用类型方法”的意思。我提供的方法适用于任意大的输入。如果不使用模幂运算等工具，处理如此大的数字是不可能的。 - John Coleman

type(sys.maxint+1) <type 'long'>这是一条语法。 - Pygirl

@KritiSahu Python3默认使用任意大的整数。您无需对类型系统进行任何操作。但您需要一个算法，可以让您计算出一个7位数字（2013258），而不必先计算出一个1.4万亿位数字。 - John Coleman

@KritiSahu 366366...366（457429086499次）将占用超过500GB的空间。即使是高端消费级计算机也只有不到100GB的RAM。除非您拥有一台超级计算机，否则这个数字将超出您的计算机容量1或2个数量级。无论如何调整Python的类型系统都无法直接表示此数字（如果您确实拥有超级计算机-肯定最好用于做类似3D蛋白质折叠之类的事情，而不是运行极其低效的算法）。 - John Coleman