令 $$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=2}^NR(k)$, 可以验证$F(10^7)=638042271 \bmod 10^9+7$。

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

本题难度:

解答

第445题中已求得 $$R(n)=\prod_{k=1}^m(p_k^{e_k}+1)-n.$$ 其中右侧的求和也是所有满足$\gcd(d,n/d)$的n的约数d之和，再对n求和，用莫比乌斯反演可以进一步简化求和项得 $$F(N)+T(N)=\sum_{n=2}^{M}n\mu(n)\left(\sum_{k=1}^{R} T(\lfloor\frac{A}{k}\rfloor)-k\lfloor\frac{A}{k}\rfloor \right)-R\cdot T(R)$$ 其中$M=\lfloor \sqrt{N}\rfloor, A=\lfloor \frac{N}{n^2}\rfloor, R=\lfloor \sqrt{A}\rfloor, T(n)=n(n+1)/2$。最终结果是$530553372$。

from sympy import sieve
import math

N=10**14
bound=10**7+1
tick=10**5

T=lambda n:n*(n+1)//2

mob=list(sieve.mobiusrange(1,bound))

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

s=0
for i in range(1,bound):
    a=N//(i*i)
    r=math.isqrt(a)
    s+=i*mob[i-1]*(sum(T(a//j)+j*(a//j) for j in range(1,r+1))-r*T(r))
    if i%tick==0:
        print(i//tick,"percent completed, current sum:",s)

print((s-T(N))%(10**9+7))