记$f(G,L,N)$为最大公约数不小于G，最小公倍数不超过L，且元素数量恰好为N的自然数集的总数。例如可以验证： \begin{align*} f(10, 100, 1) &= 91, \\ f(10, 100, 2) &= 327, \\ f(10, 100, 3) &= 1135, \\ f(10, 100, 1000) \bmod 101^4 &= 3286053。 \end{align*} 求$f(10^6, 10^{12}, 10^{18}) \bmod 101^4$。

本题难度:

解答

记$g(k,N)$是最大公约数为1，最小公倍数为k，且元素数量恰好为N的自然数集的总数。

很显然只需将每一个这样的数集作缩放就可得到一个题面中所要求的数集，因此有 $$f(G,L,N)=\sum_{k=1}^{\lfloor \frac{L}{G}\rfloor}g(k,N)\cdot(\lfloor\frac{L}{k}\rfloor-G+1).$$ 设k的素因子分别是$p_1,\ldots, p_s$，记：

X是所有元素都能整除k，且元素数量恰好为N的自然数集的总数。

$A_i$是所有元素都能被$p_i$整除，且元素数量恰好为N的自然数集的总数。

$B_i$是所有元素都能整除$k/p_i$，且元素数量恰好为N的自然数集的总数。

那么 $$g(k,N)=\left|X\setminus \left(\bigcup_i A_i\cup B_i\right)\right|.$$ 依次计算即可得最终结果$84664213$。

注：因用到sympy库（作质因数分解）和math.prod函数，以下代码为Python 3 。

import sympy,math

g=lambda L,N,m:math.prod((pow(e+1,N,m)-2*pow(e,N,m)+pow(e-1,N,m))%m for p,e in sympy.factorint(L).items())

f=lambda G,L,N,m:sum((b-G+1)*g(k,N,m)%m for k in range(1,L//G+1) if (b:=L//k)>=G)%m
    
print(f(10**6,10**12,10**18,101**4))