A - M
【题解】2019年广东工业大学腾讯杯新生程序设计竞赛_技术交流_牛客网 (nowcoder.com)
N
首先,我们对 限制一下范围:。
证:如果有 ,则 , 没有可选的值。
思路一
对原式进行变形:
观察这个式子,格式与十字相乘很像。我们把缺的一项补齐:
所以问题转化为当 时,有多少 满足 是 的因子。
注意之前限定的范围:,所以 一定是正数。所以只用考虑 作为正因子时的个数即可。
当 的值确定后, 的值也能确定。最终答案变为求 的正因子数。
思路二
假设没有看出十字相乘,设 (由之前我们限定的范围得出 只能为正整数),则原式变为:
我们消去分母,得到:
由于 且 ,所以要求 是正整数。
所以问题转化为求 的正因子个数。
求正因子数
根据唯一分解定理,任意一个正整数要么是质数,要么可以唯一分解为两个或以上从小到大质数的积。我们不妨设:
其中 是质数。我们由此可以得到:
要求 的因子,只需要从中选取质数相乘即可。选取的方案数可以通过乘法原理计算,最终为:
现在问题转化为如何求 ,我们以求 为例。
含有 因子的乘数有 ,一共有 个。
含有 因子的乘数有 ,一共有 个,同时注意每一个都已经作为 的因子出现了一次。
含有 因子的乘数有 ,一共有 个,同时注意每一个都已经作为 的因子出现了两次。
所以可以得到
全部评论
(0) 回帖