【最大因子数】

最大因子数

Time Limit : 10000/5000ms (Java/Other) Memory Limit : 65535/65535K (Java/Other)

Total Submission(s) : 39 Accepted Submission(s) : 17

Font: Times New Roman | Verdana | Georgia

Font Size: ← →

Problem Description

定义f(n)为整数n的因子数，如f(9) = 3（分别是1,3,9）.
定义g(n)=k,整数k是满足f(k) = max{f(i)|0<i<=n}的最小整数,现在给出n让你求g(n).

Input

首先输入一个整数t（t<=10^5）表示测试数据的组数。
接下来t行测试数据每行为一个正整数ai（ai<=10^7）表示要你求g(ai).

Output

对于每个测试数据输出g(ai).

Sample Input

Sample Output

Author

jxust_acm

Source

xianbin5

 1 #include <iostream>
 2 #include <fstream>
 3 #include <stdio.h>
 4 
 5 namespace ismdebug
 6 {
 7     using namespace std;
 8     ifstream cin ("in.dat", ios::in);
 9 };
10 
11 //using ismdebug::cin;
12 using std::cin;
13 using std::cout;
14 using std::endl;
15 /* 前面的命名空间之类的你就别管了 */
16 /***********************************************************************************/
17 #define iMAXN 10000200
18 
19 int iMapCount[iMAXN];
20 
21 void iMakeMapCount()/*这个是一个简单的打表，里面计算的结果是每一个数对应的因子的个数*/
22 {
23     for (int i = 0; i < iMAXN; i++)
24     {
25         iMapCount[i] = 0;/*初始置为0，因为后面是从1开始的，如果解决浪费时间的话，可以置为1，后面就从2，开始。*/
26     }
27 
28     for (int i = 1; i*2 <= iMAXN; i++)/*打表核心代码段，当i = n的时候，1*n,2*n,3*n,4*n……都是n的倍数，那么n都是他们的因子
29     那么就继续往后找，只要一直在所求范围里面就够。注意，看到后面的 j+=i了吧。那个很重要的。
30     */
31     {
32         for (int j = i; j <= iMAXN; j += i)
33         {
34             iMapCount[j]++;/*表示找到一个倍数，那么就++咯。*/
35         }
36     }
37 }
38 
39 void iScanner() /*为什么叫做scanner呢？因为这里是整理，找到之前出现的因子最多的数。*/
40 {
41     int iFlag = 1;
42     int iMaxCount = iMapCount[iFlag];
43 
44     for (int i = 2; i < iMAXN; i++)
45     {
46         if (iMapCount[i] > iMaxCount) /*找到了存在因为更多的数了，然后替换*/
47         {
48             iFlag = i;
49             iMaxCount = iMapCount[i];
50             iMapCount[i] = i;
51         }
52         else/*悲剧，没有找到啊，那么就用之前最大的来替换他咯，因为是表示这个以及这个之前出现的因子数最多的那个数*/
53         {
54             iMapCount[i] = iFlag;
55         }
56     }
57 }
58 
59 void iOutputTest() /* 测试输出 iMapCount[] 里面的数值的，后面屏蔽掉了。*/
60 {
61     for (int i = 1; i <= 100; i++)
62     {
63         cout << i << " " << iMapCount[i] << endl;
64     }
65 }
66 
67 int main()
68 {
69     iMakeMapCount(); /* 第一便打表 */
70     iScanner(); /*打表完之后进行整理，我称之扫描*/
71     //iOutputTest();
72     int t;
73     scanf("%d", &t);
74     while (t--)
75     {
76         /*打表完成之后就爽了，接下来就输入则输出就是了。同学说iScanner函数可以不用的，但是想过没有，输入数据是很多组，，5000啊，
77         所以我还是先打表吧。然后scanner、一遍吧。
78         */
79         int iNum;
80         scanf("%d", &iNum);
81         printf("%d\n", iMapCount[iNum]);
82     }
83     return 0;
84 }
85 
86 // end
87 // ism