【问题描述】
求1~N当中约数个数最多的数的个数。
【输入格式】 T组数据 每一组只有一行。这一行有一个数N（1≤N<10^18）。
simple input 3 13 9 1000000000000000000 simple output 13 9 103680 分析： 直接暴力肯定会超时，那么怎么处理呢？？？
根据唯一分解定理，我们可以知道一个整数是可以分解成素数的乘积的 那么就可以得到： 将任意自然数 n (n>2) 分解
n=p1k1p2k2p3k3…pmkm(p1<p2<⋯<pm)
则 n 的因子数为 (k1+1)(k2+1)…(km+1) 但是直接这样拆其因子也会引起超时的，那么就需要去剪枝优化，肯定会有小伙伴们会这样去想，枚举素因子的个数，先从最小的开始，然后选择0个p1,1个p1,2个p1……，然后再去找0个p2,1个p2,2个p2……，将这些遍历完之后去更新答案，不幸的是……………………这样去做还是会超时的(ಥ_ಥ)
是不是还可以再去优化剪枝呢，答案是对； 我们看以下的例子：
6=2 * 3 ；10=2*5
6和10的质因数分解“模式”完全相同，所以它们的约数个数是相同的。但是由于3<5，所以6<10。
12=22*3 18=32*2
个数都是一样的，问啥不去找最小的那一个呢，因此我们在求其个数的时候可以加一下限制条件，即： 可以在枚举时进行一个优化，使得枚举到的数字中2的指数不小于3的指数，3的指数不小于5的指数……这样我们就能够得到质因数分解“模式”相同的最小数
#include <iostream> #include <algorithm> #include <string> #include <map> #include <cstring> #include <cmath> #include <queue> #include <cstdio> #include <vector> #include <set> #include <stack> using namespace std; typedef long long ll; const int N = 1e6+10; const int INF=0x3f3f3f3f; const ll LINF=0x3f3f3f3f3f3f3f3f; const int MOD=1e9+7; #define rep(i,a,b) for(int i=a;i<=b;i++) #define Abs(x) ((x)>=0?(x):-(x)) ll n,ans; //假设给出的N是由连续相乘的素数得来的，那么最多存在当前这些素数的乘积 int prime[20] = {0,2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53};//1--16 void dfs(ll m,ll res,int i,int limit){//m指当前的值，res代表因子个数，i代表当前需要乘的素因子是谁，limit是最多当前素因子能枚举的个数 ans=max(ans,res);//更新答案 ll cnt=1;//cut用于计当前素数的个数+1，因为是由上述的公式得到的； for(int j=1;j<=limit;j++) { cnt++; if(n/m<prime[i])//如果下一次再乘当前的素数会大于n的话就跳出,为啥不写成if(n<m*prime[i])呢？ break;//因为有可能会越界，超出longlong，那么就会引起死循环或者爆栈 m*=prime[i]; if(m<=n) dfs(m,res*cnt,i+1,j); } } int main() { #ifndef ONLINE_JUDGE freopen("in.txt","r",stdin); #endif // ONLINE_JUDGE int T; scanf("%d",&T); while(T--){ scanf("%lld",&n); ans=0; dfs(1,1,1,61); printf("%lld\n",ans); } return 0; }