体现在 \operatorname{RHS} 中，考虑其贡献到 b 中所有位的方案数。 含有因子 p 的 b_i 至多一个，使 b_i 含有 p 的分配 p 的方案数为 c_i，故其对 \operatorname{RHS} 的贡献是 \times (\sum_{i=1}^nc_i+1)，1 表示所有 b_i 不含 p。
考虑对所有合法的 b 计算贡献，一个 b 的贡献即为满足 \forall i,b_i|a_i 且 a_i\in [1,m] 的 a 的个数。考虑不断加入元素到 b 中，可重集 \{b_1,\dots,b_n\} 的形式必定是若干个 1 加上若干不重元素，设不重元素的部分构成的集合为 T，考虑一个 T 的贡献，为 A_{n}^{n-|T|}m^{n-|T|}\prod_{x\in T}\lfloor\frac{m}{x}\rfloor。
你发现前面两项都只和 |T| 有关，考虑对于所有 k 计算所有 |T|=k 的 \prod_{x\in T}\lfloor\frac{m}{x}\rfloor。你要求 T 不重，且其中任意两个元素 \gcd 为 1。设 f_{i,S} 表示当前 |T|=i，当前 T 中所有元素的所有质因子构成的集合为 S，这样前提下上式的求和。
则转移为 f_{i+1,S|D(x)}\stackrel{+}\leftarrow f_{i,S}，其中 D(x) 为 x 的质因子集合，转移条件是 S\cap D(x)=\empty。
考虑优化，该算法瓶颈在第二维状态设计，考虑将所有质因子分成 \le \sqrt m 和 >\sqrt m 两类，尝试只记录第一类。
你发现记录一个质因子的目的是保证后面加入的数不会再有这个质因子，那不妨改变转移顺序使得后面加入的数不会再含有这个质因子。而一个数不会有两个 >\sqrt m 的质因子，故对 [2,m] 这些数按最大质因子从小到大的顺序加入，复杂度 O(m\pi(m)2^{\pi(\sqrt m)})。