ZOJ 2562 More Divisors
More Divisors
64-bit integer IO format: %lld Java class name: Main
Everybody knows that we use decimal notation, i.e. the base of our notation is 10. Historians say that it is so because men have ten fingers. Maybe they are right. However, this is often not very convenient, ten has only four divisors -- 1, 2, 5 and 10. Thus, fractions like 1/3, 1/4 or 1/6 have inconvenient decimal representation. In this sense the notation with base 12, 24, or even 60 would be much more convenient.
The main reason for it is that the number of divisors of these numbers is much greater -- 6, 8 and 12 respectively. A good quiestion is: what is the number not exceeding n that has the greatest possible number of divisors? This is the question you have to answer.
Input:
The input consists of several test cases, each test case contains a integer n (1 <= n <= 1016).
Output:
For each test case, output positive integer number that does not exceed n and has the greatest possible number of divisors in a line. If there are several such numbers, output the smallest one.
Sample Input:10 20 100Sample Output:
6 12 60
Source
Author
![](https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif)
1 #include <bits/stdc++.h> 2 using namespace std; 3 typedef long long LL; 4 const LL INF = 0x3f3f3f3f3f3f3f3f; 5 const int maxn = 1010; 6 int p[maxn],tot; 7 bool np[maxn] = {true,true}; 8 void init(){ 9 tot = 0; 10 for(int i = 2; i < maxn; ++i){ 11 if(!np[i]) p[tot++] = i; 12 for(int j = 0; j < tot && p[j]*i < maxn; ++j){ 13 np[p[j]*i] = true; 14 if(i%p[j] == 0) break; 15 } 16 } 17 } 18 19 LL ret,tsum,x; 20 21 void dfs(int cur,LL sum,LL val){ 22 if(sum > tsum || sum == tsum && val < ret){ 23 ret = val; 24 tsum = sum; 25 } 26 for(int i = 1; i < 61; ++i){ 27 val *= p[cur]; 28 if(val > x) break; 29 dfs(cur + 1,sum*(i + 1),val); 30 } 31 } 32 int main(){ 33 init(); 34 while(~scanf("%lld",&x)){ 35 ret = INF; 36 tsum = 1; 37 dfs(0,1,1); 38 printf("%lld\n",ret); 39 } 40 return 0; 41 }
相关文章
- Using more than one index per table is dangerous?
- Journey or destination- which is more important?
- hdu 1856 More is better(并查集)
- NYOJ 232 How to eat more Banana
- mongodb Sort operation used more than the maximum 33554432 bytes of RAM
- [LeetCode] Employees Earning More Than Their Managers 员工挣得比经理多
- 《GhostNet:More Features from Cheap Operations》论文笔记
- 文件内容操作命令 cat、more、less、head、tail、wc、grep 命令详情
- 1068 Find More Coins
- 论文阅读笔记An Adaptive Iterative Inpainting Method with More InformationExploration