开刷水题

1109 - False Ordering    PDF (English)StatisticsForum Time Limit: 1 second(s)Memory Limit: 32 MB

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 n^th number after ordering.

Sample Input

Output for Sample Input

5

1

2

3

4

1000

Case 1: 1

Case 2: 997

Case 3: 991

Case 4: 983

Case 5: 840

题意：

就是呢，在 1 - 1000 数据之间有一张顺序表，排序的依据是：

因子个数多的排到后面，因子个数相等的时候，数字较大的排到前面。

此时呢，键入一个 1 - 1000 的数字 n ，问在当前表中第 n 个数字是多少。

思路：

结构体模拟一下就好了，其他的方法也没有深究。

sort 排序肯定会打乱数字顺序，引入一个变量记录它的顺序就 ok 啦。

感想：

好友没更博客了，明天就是蓝桥杯了，就只是在这里留念一下。毕竟没有自己的名额昂，有个好师父，但是没珍惜....手速不行，脑袋转不开，只差四个名额...也怪自己当时没把握好方向，兴趣颇多吧。现在就好好的跟队友一起敲 bug 吧。

hpu的 ACMer 们，明天凯旋。

菜菜的 AC CODE：

#include<cstdio> #include<cmath> #include<iostream> #include<algorithm> #include<string> #include<map> using namespace std; typedef long long ll; const int mz = 1e3+2; const double pi = 2.0*acos(0.0); struct Q { int i;/*保留当前数字*/ int sum; } a[mz]; int get(int x) { int sum = 0; for(int j = 1; j <= sqrt(x); j++) { if(x % j == 0) sum += 2; } int tp = sqrt(x); if(tp * tp == x) sum--; return sum; } bool cmp(Q x, Q y) { if(x.sum != y.sum) return x.sum < y.sum;/*因子个数升序*/ return x.i > y.i;/*因子相等时降序*/ } void init() { for(int i = 1; i <= 1000; i++) { a[i].i = i; a[i].sum = get(i); } sort(a+1, a+1+1000, cmp); } int main() { int T, kc = 1; init(); scanf("%d", &T); while(T--) { int n; scanf("%d", &n); printf("Case %d: ", kc++); printf("%d\n", a[n].i); } return 0; }