问题 D: 磊哥的密码箱（搜索）

磊哥有个密码箱，里面装的都是令磊哥羞羞的东西。 箱子的密码是[1,n]里面的约数最多的数的约数数目。 磊哥的女朋友想知道磊哥到底装的是什么东西？她需要你的帮助。

输入

输入一个整数T，表示有T个测试数据 下面T行，每行输入一个正整数n。

输出

对每个n，输出对应一行一个正整数表示[1,n]里最多约数的数的约数个数。

样例输入

复制样例数据

2 13 9 样例输出 6 4

提示

100%的数据满足：1 ≤ n ≤ 1,000,000,000,000,000,000.

对于任意一个整数，如果把一个数因数分解的话，那么我们可以考虑搜索质因子。

把一个数表示成质因数幂的形式为：

　　A = x1^p1∗x2^p2∗x3^p3∗...∗xn^pn

则该数的约数个数为(p1+1)∗(p2+1)∗(p3+1)∗...∗(pn+1)(p1+1)∗(p2+1)∗(p3+1)∗...∗(pn+1)根据这个公式来检验当前答案是否最优。

#include<bits/stdc++.h> #define int long long using namespace std; int p[] = {0,2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59}; int n,ans; void dfs(int pos,int num,int sum,int len) { if(sum > n) return; ans = max(ans,num); for(int i = 1;i <= len; i++) { int tmp = pow(p[pos],i); if(sum > n / tmp) continue; dfs(pos + 1,num * (i + 1),sum * tmp,i); } } signed main() { ios::sync_with_stdio(false); cin.tie(0); int T; cin >> T; while(T--) { ans = 0; cin >> n; dfs(1,1,1,30); cout << ans << endl; } return 0; }