链接
题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=1053
神犇题解:http://medalplus.com/?p=2105
题解
这种题看一眼就会去想找规律吧?
打个表看一看大概是这样:
于是我们可以找到如下规律:
1.质因数是连续的,也就是说我们只用考虑37及之前的质因数
2.较大的质因数个数一定少于较小的质因数的个数
于是我们就可以写个深搜
枚举出所有符合条件的数
然后用这些数去更新答案辣!
Code
#include<bits/stdc++.h> #define LL long long using namespace std; const int SZ = 12; int n,num,vout,pri[]={0,2,3,5,7,11,13,17,19,23,29,31,37}; inline int read(){ char c=getchar(); int ret=0,f=1; while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();} while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();} return ret*f; } int DFS(int t, int last, int w, int v) { if (t == 13) { if (v == num) { vout = min(vout, w); } else if (v > num) { vout = w; num = v; } } else { for (int i=0,cur=1;i<=last;i++,cur*=pri[t]) { if ((LL)cur * w > n) break; else { DFS(t+1, i, w*cur, v*(i+1)); } } } } int main(){ if ((n=read()) == 1) { puts("1"); } else { DFS(1,30,1,1); printf("%d\n",vout); } return 0; }
Thank you for the auspicious writeup. It in fact was a amusement account it. Look advanced to far added agreeable from you! By the way, how can we communicate?
fantastic points altogether, you simply gained a brand new reader. What would you suggest in regards to your post that you made a few days ago? Any positive?