磊哥有个密码箱，里面装的都是令磊哥羞羞的东西。
箱子的密码是[1,n]里面的约数最多的数的约数数目。
磊哥的女朋友想知道磊哥到底装的是什么东西？她需要你的帮助。
2
13
9
6
4
100%的数据满足：1 ≤ n ≤ 1,000,000,000,000,000,000.
解决这道题，涉及一点点数论的知识，点击查看。看完在看这道题（大佬随意QAQ）
具体的思路呢其实就是贪心。
根据唯一分解定理和约数个数定理，我们知道对于每一个数，写成标准分解式（n = p1^a1*p2^a2...pk^ak），约数的个数为(a1+1)*(a2+1)...*(ak+1)，为了使的约数的个数尽量多，p应该尽量选小的。
#include <iostream> #include <bits/stdc++.h> using namespace std; typedef long long ll; ll n,ans; int p[30]={0,2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61}; ll qpow(ll a,ll b) //快速幂 { ll ret=1; while(b) { if (b&1) ret=ret*a; a=a*a; b>>=1; } return ret; } void dfs(ll poi,ll num,ll val,ll len) //枚举第几个质数poi，现在有几个约数，现在的值，ai的最大值 { if (val>n) return; if (val<=n) ans=max(ans,num); for (int i=1; i<=len; i++) //相当于枚举这位质数对应的a { ll t=qpow(p[poi],i); if (t>n/val) return; dfs(poi+1,num*(i+1),val*t,i); } return; } int main() { int T; cin>>T; while(T--) { ans=0; scanf("%lld",&n); dfs(1,1,1,18); printf("%lld\n",ans); } return 0; }
原文：https://www.cnblogs.com/ztdf123/p/10931785.html