Description
We define b is a Divisor of a number a if a is divisible by b. So, the divisors of 12 are 1, 2, 3, 4, 6, 12. So, 12 has 6 divisors.
Now you have to order all the integers from 1 to 1000. x will come before y if
1) number of divisors of x is less than number of divisors of y
2) number of divisors of x is equal to number of divisors of y and x > y.
Input
Input starts with an integer T (≤ 1005), denoting the number of test cases.
Each case contains an integer n (1 ≤ n ≤ 1000).
Output
For each case, print the case number and the nth number after ordering.
Sample Input
5
1
2
3
4
1000
Sample Output
Case 1: 1
Case 2: 997
Case 3: 991
Case 4: 983
Case 5: 840
统计一个整数n的因子个数的方法：将n进行素因子分解，n=(q1^r1)*(q2^r2)*...*(qi^ri)，则n的因子数为（r1+1）*(r2+1)*...*(ri+1).
因为对于每个q，其对应的指数为r，q可取0个，1个，...，r-1个。
AC Code：
1 #include2 #include 3 #include 4 #include 5 using namespace std; 6 7 int dr[1001], num[1001]; //dr[i]是i的因子个数，num[i] = i 8 int d[500], di = 0; 9 bool p[1001];10 11 bool cmp(const int& a, const int& b)12 {13 if(dr[a] != dr[b]) return dr[a] < dr[b];14 return a > b;15 }16 17 void Init_Prime()18 {19 memset(p, 0, sizeof(p));20 p[1] = 1;21 for(int i = 2; i < 1001; i++)22 {23 if(!p[i])24 {25 d[di++] = i;26 for(int j = 2; j * i < 1001; j++)27 p[i*j] = 1;28 }29 }30 //for(int i = 0; i < di; i++) cout << d[i] << ' ';31 return ;32 }33 34 void Cal(int x)35 {36 int t = x;37 int sum = 1, cnt;38 for(int i = 0; d[i] <= t / 2 && i < di; i++)39 {40 cnt = 0;41 while(x % d[i] == 0)42 {43 cnt++;44 x /= d[i];45 }46 sum *= (cnt + 1);47 }48 if(!p[t]) sum *= 2;49 dr[t] = sum;50 return ;51 }52 53 int main()54 {55 int t, n, ca = 1;56 scanf("%d", &t);57 Init_Prime();58 for(int i = 1; i < 1001; i++)59 {60 num[i] = i;61 Cal(i);62 }63 //for(int i = 1; i < 30; i++) cout << i << ' ' << dr[i] << endl;64 sort(num + 1, num + 1001, cmp);65 while(t--)66 {67 scanf("%d", &n);68 printf("Case %d: %d\n", ca++, num[n]);69 }70 return 0;71 }