因数最多的数【DFS】
一、题目：
蒜头君对一个数的因数个数产生了兴趣，他想知道在1~n的范围内，因数个数最多的数是多少。如果有多个这样的数，他想知道最小的那个。
| 输入格式 | 第一行一个整数T，表示数据的组数 接下来T行，每行一个正整数n 1<=T<=100,1<=N<=10^16 |
| 输出格式 | 一共输出T行，每行1个正整数表示最多因数个数的数 |
I
Input:
3
10
100
1000Output:
6
60
840二、分析
这个数的范围在10^16,显然线性找一遍是不能承受的。
解决的一种方式是枚举法。我们知道一个数N可以表示成 ,其中pi为质数。他的因数个数为
。
如12 = 2^2 * 3…^1，那么他的因数个数有（2 + 1）×（1+1）= 6.( 即质数2选0个，1个，2个共3中情况，质数3选0个，1个两种情况，共6种情况。12的因数为1,2,3,4,6,12共6个）。
本题中，我们发现，前15个质数的积大于10^16。于是我们可以像八皇后枚举每个皇后的列的位置一样，本题可以枚举这15个质数每个质数的个数。
同时我们还有注意以下的剪枝情况：
- 第i个质数的次数一定大于等于第i+1个质数的次数。因为我们求最小的那个因数最多的数。如2^2 * 3 ^ 3 = 4 * 27 = 108.有(2 + 1) *(3 + 1) = 12个质数，但是如果我们把大小质数的次数交换一下。2^3 * 3 ^ 2 = 8 * 9 = 72.同样也有12个质数。因数个数不变，但是数变小了。这样一来可以大大减少枚举的计算量。
- 如果当前枚举质因子得到的数大于N，那剪枝即可
三、代码：
#include
using namespace std;
typedef long long LL;LL n, ans, mc; //mc因数个数最大值，ans因数个数最多的那个数
const int prime[15] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47};/* u: 当前正在考虑那个质因数？m: 当前这个质因数的最大次数是多少？ x: 当前这个数是多少？cnt:当前这个数的因数有多少？
*/
void dfs(int u, int m, LL x, LL cnt) {if (cnt > mc) {mc = cnt;ans = x;} else if (cnt == mc && x < ans) {ans = x;}if (u == 15) return;for (int i = 1; i <= m; i++) {x = x * prime[u];if (x > n) break;dfs(u + 1, i, x, cnt * (i + 1)); //这里第2个参数是i，是第i个因子次数>=第i+1个因子次数，减少搜索量。 }
}int main() {int T;cin >> T;while (T--) {cin >> n;mc = 0;dfs(0, 60, 1, 1); //从第0个质数开始考虑，初始的质数的次数不超过60，初始的数为1，初始的数的因数个数为1.cout << ans << endl;}return 0;
}
本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！