A - M

【题解】2019年广东工业大学腾讯杯新生程序设计竞赛_技术交流_牛客网 (nowcoder.com)

N

首先，我们对 限制一下范围：。

证：如果有 ，则 ， 没有可选的值。

思路一

对原式进行变形：

观察这个式子，格式与十字相乘很像。我们把缺的一项补齐：

所以问题转化为当 时，有多少 满足 是 的因子。

注意之前限定的范围：，所以 一定是正数。所以只用考虑 作为正因子时的个数即可。

当 的值确定后， 的值也能确定。最终答案变为求 的正因子数。

思路二

假设没有看出十字相乘，设 （由之前我们限定的范围得出 只能为正整数），则原式变为：

我们消去分母，得到：

由于 且 ，所以要求 是正整数。

所以问题转化为求 的正因子个数。

求正因子数

根据唯一分解定理，任意一个正整数要么是质数，要么可以唯一分解为两个或以上从小到大质数的积。我们不妨设：

其中 是质数。我们由此可以得到：

要求 的因子，只需要从中选取质数相乘即可。选取的方案数可以通过乘法原理计算，最终为：

现在问题转化为如何求 ，我们以求 为例。

含有 因子的乘数有 ，一共有 个。

含有 因子的乘数有 ，一共有 个，同时注意每一个都已经作为 的因子出现了一次。

含有 因子的乘数有 ，一共有 个，同时注意每一个都已经作为 的因子出现了两次。

所以可以得到