16年青岛网络赛 1001 I Count Two Three

题目链接：http://acm.hdu.edu.cn/contests/contest_showproblem.php?pid=1001&cid=723

I Count Two Three
Time Limit: 3000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 3582 Accepted Submission(s): 1094

Problem Description
I will show you the most popular board game in the Shanghai Ingress Resistance Team.
It all started several months ago.
We found out the home address of the enlightened agent Icount2three and decided to draw him out.
Millions of missiles were detonated, but some of them failed.

After the event, we analysed the laws of failed attacks.
It's interesting that the i-th attacks failed if and only if i can be rewritten as the form of 2a3b5c7d which a,b,c,d are non-negative integers.

At recent dinner parties, we call the integers with the form 2a3b5c7d "I Count Two Three Numbers".
A related board game with a given positive integer n from one agent, asks all participants the smallest "I Count Two Three Number" no smaller than n.

Input
The first line of input contains an integer t (1≤t≤500000), the number of test cases. t test cases follow. Each test case provides one integer n (1≤n≤109).

Output
For each test case, output one line with only one integer corresponding to the shortest "I Count Two Three Number" no smaller than n.

Sample Input
10
1
11
13
123
1234
12345
123456
1234567
12345678
123456789

Sample Output
1
12
14
125
1250
12348
123480
1234800
12348000
123480000

题目大意：输入一个不超过10的9次方的整数n，然后输出一个最接近n且不小于n的整数同时这个数还满足

　　　　　这样的格式（2^a*3^b*5^c*7^d、 a，b，c，d可为任意非负整数）

解题思路：暴力打表用一四重循环求出所有范围内且满足2^a*3^b*5^c*7^d格式的整数在sort排序后二分查找。

AC代码：

 1 #include<stdio.h>
 2 #include<iostream>
 3 #include<algorithm>
 4 #include<math.h>
 5 using namespace std;
 6 
 7 long long a[1100000];
 8 
 9 int main()
10 {
11     int t = 0, i, j, k, l, n;   //求出所有范围内且满足2^a*3^b*5^c*7^d格式的整数
12     for(i = 0; (long long)pow(2,i) < 1100000000; i++)
13     for(j = 0; (long long)pow(2,i)*pow(3,j) < 1100000000; j++)
14     for(k = 0; (long long)pow(2,i)*pow(3,j)*pow(5,k) < 1100000000; k++)
15     for(l = 0; (long long)pow(2,i)*pow(3,j)*pow(5,k)*pow(7,l) < 1100000000; l++)
16         a[t++] = (long long)(pow(2,i)*pow(3,j)*pow(5,k)*pow(7,l)+1e-10);
17     sort(a, a + t);
18     scanf("%d", &n);
19     while(n--)
20     {
21         scanf("%d", &l);
22         if(l == 1)    //如果是1输出它本身 
23             printf("1
");
24         else
25         {    
26             i = t / 2;
27             j = 0;
28             k = t;
29             while(1)       //二分查找 
30             {
31                 if(l <= a[i] && l > a[i-1])
32                 {
33                     printf("%d
", a[i]);
34                     break;
35                 }
36                 else if(l < a[i])
37                 {
38                     k = i;
39                     i = (j+i)/2;
40                 }
41                 else
42                 {
43                     j = i;
44                     i = (i+k)/2;
45                 }
46             }
47         }    
48     }
49 }

View Code

注意：打表时不能只求10^9之内的数，

　　　需要找超出10^9一些的数。否则容易在边界处出错。