计算 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

如何解决这个问题？

Answer 1

没有适用于大量问题的简单解决方案。您需要使用一些聪明的代数 and/or 数论。 366, 366366, 366366366, ... 是几何级数的部分和。有一个用于对它们求和的标准公式，但不幸的是，它涉及除法，这对模运算来说效果不佳。 This answer 对于如何计算它们的问题给出了一个聪明的递归解决方案，它类似于模幂运算的标准方法。在 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

例如，

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

几乎是即时计算的。

计算 python 中较大数字的模数

Calculating modulus for larger numbers in python

python

math

python-3.x

modular-arithmetic