O中第一个N个自然数的总和（N中的位数）

Question

我正在尝试编写一个程序来查找前 N 个自然数的总和，即 1 + 2 + 3 + .. + N 模 1000000009

我知道这可以通过使用公式 N * (N+1) / 2 来完成，但我正在尝试找到一种递归函数来计算总和。

我尝试在网上搜索，但没有得到任何解决方案。

实际上，这里的问题是数字N最多可以有100000位。

所以，这是我到目前为止尝试过的方法。

首先，我尝试将数字拆分为每个长度为 9 的部分，然后将它们转换为整数，以便我可以使用整数运算符执行算术运算。

例如，数字52562372318723712将被拆分为52562372和318723712。但是我没有找到操纵这些数字的方法。

然后我又试着写了一个函数如下：

def find_sum(n):
    # n is a string
    if len(n) == 1:
        # use the formula if single digit
        return int(int(n[0]) * (int(n[0]) + 1) / 2)

    # I'm not sure what to return here
    # I'm expecting some manipulation with n[0] 
    # and a recursive call to the function itself

    # I've also not used modulo here just for testing with smaller numbers
    # I'll add it once I find a solution to this
    return int(n[0]) * something + find_sum(n[1:])

我在这里找不到 something。可以这样解决吗？或者还有其他方法吗？

注意：我更喜欢与上述功能类似的解决方案，因为我想修改此功能以满足我想在此处询问之前自己尝试的其他要求。但如果不可能，任何其他解决方案也会有所帮助。

请给我任何解决问题的提示。

Answer 1

您最好的选择是只使用 N*(N+1)/2 公式——但要使用它 mod p。唯一棘手的部分是解释除以 2——这必须是 2 mod p 的倒数。对于 p 素数（或简单地对于 p 奇数），这很容易计算：它只是 (p+1)//2.

因此：

def find_sum(n,p):
    two_inv = (p+1)//2 #inverse of 2, mod p
    return ((n%p)*((n+1)%p)*two_inv)%p

例如：

>>> find_sum(10000000,1000000009)
4550000
>>> sum(range(1,10000001))%1000000009
4550000

请注意，如果您为 p 传递偶数，上述函数将失败。

On Edit 正如@user11908059 所观察到的，可以省去乘以 2 的 mod 元逆的乘法。作为一个额外的好处，这种方法不再取决于 modulus 是否为奇数：

def find_sum2(n,k):
    if n % 2 == 0:
        a,b = (n//2) % k, (n+1) % k
    else:
        a,b = n % k, ((n+1)//2) % k
    return (a*b) % k

O中第一个N个自然数的总和（N中的位数）

Sum of 1st N natural numbers in O(no. of digits in N)

python

algorithm

sum

biginteger