模余和

数列$a_n$的初值为$a_1=1$，递推式为： $$a_n=(\sum_{k=1}^{n-1}k·a_k) \bmod n.$$ 它的前10项分别是：1,1,0,3,0,3,5,4,1,9。记$f(N,M)$为满足以下条件的数对$(p,q)$的数量： $$1 \le p \le q \le N \text{ 且 } (\sum_{t=p}^{q}a_i) \text{ mod } M=0.$$ 可以验证$f(10,10)=4$，满足要求的四对数对分别是(3,3)、(5,5)、(7,9)和(9,10)。

此外还有$f(10^4,10^3)=97158$。求$f(10^12,10^6)$。

本题难度:

解答

根据OEIS A372865的信息，该数列满足 \begin{align*} a_{6i}&=3i \\ a_{6i+1}&=4i+1 \\ a_{6i+2}&=3i+1 \\ a_{6i+3}&=i \\ a_{6i+4}&=6i+3 \\ a_{6i+5}&=i \end{align*} 记$S_n=\sum_{i=1}^na_i$，则有 \begin{align*} S(6i)&=9i^2-i \\ S(6i+1)&=9i^2+3i+1 \\ S(6i+2)&=9i^2+6i+2 \\ S(6i+3)&=9i^2+7i+2 \\ S(6i+4)&=9i^2+13i+5 \\ S(6i+5)&=9i^2+14i+5 \end{align*} 记 $$c_k=\left|\{1\le n\le N: S(n)=k \pmod M\}\right|$$ 显然 $$S(i+M)=S(i) \pmod M,$$ 因此只需考虑1到M之间的m，而最终结果是

$$\sum_{k=0}^{M-1}\binom{c_k}{2}=1966666166408794329.$$

N=10**12
M=10**6

c=[0]*M
b=[0]*6

for i in range(M):
    b[0]=(9*i*i-i)%M
    b[1]=(9*i*i+3*i+1)%M
    b[2]=(9*i*i+6*i+2)%M
    b[3]=(9*i*i+7*i+2)%M
    b[4]=(9*i*i+13*i+5)%M
    b[5]=(9*i*i+14*i+5)%M
    for j in range(6):
        c[b[j]]+=(N-j-6*i+6*M)/(6*M)

print sum(c[i]*(c[i]-1)/2 for i in range(M))