令$F(n, d)$为n的因数中尾数为d的数的总数。

例如$F(84, 4)=3$，因为84的因数有1, 2, 3, 4, 6, 7, 12, 14, 21, 28, 42, 84，其中4, 14, 84这三个数的尾数为4。

可以验证$F(12!, 12)=11, F(50!, 123)=17888$。

求$F(10^6!, 65432) \bmod 10^{16} + 61$。

本题难度:

解答

设$p^{m_p}$是$10^6!$的因子中素数$p$的最大幂。设$d$是$10^6!$的一个因子，则有 $$d=\prod_{p<10^6}p^{a_p}.$$ 若$d$模$10^5$余$65432$，则显然$2^{a_2}$和$5^{a_5}$分别是$2$和$5$可以整除$\gcd(10^5,65432)$的最大幂，从而$a_2=3, a_5=0$，亦即需要 $$\prod_{\substack{p<10^6 \\ p\neq 2,5}}p^{a_p}=8179 \pmod 12500.$$ 乘法群$\mathbb Z_{12500}^*$共有$\varphi(12500)=5000$个元素，注意到$12500$只有$2$和$5$两个约数，因此对上式左侧的每个$p$而言$x\mapsto px$都是$\mathbb Z_{12500}^*$上的自同构。

注意到（！）以下集合中的元以相等的重数完全地分布在$\mathbb Z_{12500}^*$（$\mathbb Z_{12500}^*$中的每个元素都出现且出现的次数相同）中 $$S=\{3^u\cdot401^v\cdot 677^w: 0\le u\le m_3, 0\le v\le m_{401}, 0\le w\le m_{677}\}.$$ 设此重数为$k$，那么对每个形如 $$d=\prod_{\substack{p<10^6 \\ p\neq 2,3,5,401,677}}p^{a_p},$$ 而言，多重集$dS$中$8169$都出现了$k$次，因此最终结果是 $$\prod_{\substack{p<10^6 \\ p\neq 2,5}}(1+a_p)\bmod 10^{16}+61=9690646731515010.$$ 注1：本题十分巧妙，但需要足够的群论知识。

注2：因使用sympy求$5000$在$\mathbb Z_{12500}^*$中的逆，以下代码为Python 3。

import sympy

n=10**6
r=5000

mod=10**16+61

s=(1+sum(n//(3**i) for i in range(1,13)))%mod

for p in sympy.primerange(6,n):
    m,q=0,p
    while n>=q:
        m+=n//q
        q*=p
    s=(s*(1+m))%mod

print(s*sympy.mod_inverse(r,mod)%mod)