swustoj-2394: JUST SORT

杂

Description

We define B is a Divisor of one 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 in total.
Now you have to order all the integers from 1 to 100000 by the following rules:
X will come before Y if
(1) the number of divisors of X is less than the number of divisors of Y
(2) the number of divisors of X is equal to the number of divisors of Y and X > Y.

Input

there are many test cases.
Each case contains an integer n (1 ≤ n ≤ 100000).

Output

For each case, print the case number and the nth number after ordering.

Sample Input

1
2
3
4
1000

Sample Output

Case 1: 1
Case 2: 99991
Case 3: 99989
Case 4: 99971
Case 5: 88741

#include<stdio.h>
#include<math.h>
#include<algorithm>
using namespace std;
struct yz
{
    int m;
    int n;
}a[100005];
int sum(int n)
{
    if(n==1)return 1;
    int s=2,x,y,i;
    x=sqrt(n);
    for(i=2;i<=x;i++)
    {
        if(n%i==0)
        {
            y=n/i;
            if(y==i)
                s++;
            else
                s+=2;
        }
    }
    return s;
}
int cmp(yz a,yz b)
{
    if(a.n==b.n)
        return a.m>b.m;
    return a.n<b.n;
}
int main()
{
    int j,n,x=1;
    for(j=1;j<100001;j++)
    {
        a[j].m=j;
        a[j].n=sum(j);
    }
    sort(a+1,a+100001,cmp);
    while(scanf("%d",&n)!=EOF)
    {
        printf("Case %d: %d\n",x,a[n].m);
        x++;
    }
    return 0;
}