对任意大于1的自然数n而言$n^{15}+1$都是合数。

记$s(n,m)$为$n^{15}+1$的所有不超过m的质因数之和。

例如$2^{15}+1=3^2\times 11\times 331$，因此$s(2,10)=3$，而$s(2,1000)=3+11+331=345$。

类似地，$10^{15}+1=7\times 11\times 13\times 211\times 241\times 2161\times 9091$，因此$s(10,100)=31$，而$s(10,1000)=483$。

求$\sum_{n=1}^{10^{11}}s(n,10^8)$。

本题难度:

解答

先用筛法找出$10^8$以下的素数，接下来对每个素数p，在模p乘法群$\mathbb Z_p^*$找出 $$q^{15}=-1 \pmod p,$$ 的所有解q，每一个q对应生成$\lfloor10^{11}-q\rfloor+1$个n，汇总即得结果$2304215802083466198$。

注：因使用sympy库的nthroot_mod方法求解q，以下代码为Python 3，代码中还打印了进度信息。

import sympy

M=10**11

target=10**8
d=[0]*target
n=2
while n < target:
    for i in range(n*n,target,n):
        d[i]=d[i]+1
    n=n+1
    while n < target and d[n]>0:
        n=n+1

print("primes generated, start checking...")
tick=10**6
s=0
for p in range(2,target):
    if d[p]==0:
        s+=sum((M-q)//p+1 for q in sympy.nthroot_mod(p-1,15,p,all_roots=True))*p
    if p%tick==0:
        print(p//tick,"percent completed, current sum:",s)

print(s)