令 $$f_{n,a,b}(x)=ax+b \pmod n,$$ 其中$a,b,x\in\mathbb Z$且$0 < a < n, 0\le b < n, 0\le x < n$。若 $$f_{n,a,b}(f_{n,a,b}(x))=f_{n,a,b}(x) \pmod n,$$ 对任意$0\le x < n$都成立，就称$f_{n,a,b}$为收缩函数。

记$R(n)$是n所对应的收缩函数的总数，并记$F(N)=\sum_{k=1}^NR(k^4+4)$, 可以验证$F(1024)=77532377300600$。

求$F(10^7)$模$10^9+7$的余数。

本题难度:

解答

在上一题中已证明 $$R(n)=\prod_{k=1}^m(p_k^{e_k}+1)-n.$$ 注意到 $$x^4+4=\left((x+1)^2+1\right)\left((x-1)^2+1\right),$$ 因此只需用筛法找出形如$x^2+1$的数的质因数分解即可，最终结果是$907803852$。

注：因需要内建函数作快速幂以及一些语法特性，以下代码为Python 3。

target=10**7+1
mod=10**9+7

p=[i*i+1 if i%2==0 else (i*i+1)//2 for i in range(target+1)]
f=[1]*(target+1)

for i in range(2,target+1):
    if (q:=p[i])>1:
        for j in range(i,target+1,q):
            m=1
            while p[j]%q==0:
                p[j]//=q
                m*=q
            f[j]=f[j]*(m+1)%mod

print("initialization completed, start computing...")

s=0
for n in range(1,target):
    u=pow(n,4,mod)+4
    v=f[n-1]*f[n+1]%mod
    if n%2==0:
        v=(v*5)%mod
    s=(s+v-u)%mod

print(s)