number of divisor.cpp

#include<bits/stdc++.h>
using namespace std ;

#define M 1005
#define pii pair<int , int >
#define mp make_pair
#define pf printf
#define sf scanf
#define sf1(a ) scanf("%d",&a)
#define pb push_back
#define mem(x, y) memset(x , y , sizeof x )
#define sf2(a, b) scanf("%d%d",&a ,&b)
#define rep(i,n) for(i = 0 ; i< n ;i++ )
#define repi(i,n) for(i = 1 ; i<= n ; i++ )

int p_arr[M ] , arr[M]  ;

struct _si{
	int var , num ;
	_si();
	_si(int a , int b )
	{
		var = a ;
		num = b ;
	}

};

vector<_si  > si ;
vector<int > divv ;

void seive(){
	int i ,j , k ;
	//mem(p_arr , 1 );
	rep(i , M ) p_arr[i] = 1 ;
	p_arr[0] = p_arr[1] = 0 ;
	for(i = 2 ; i < M ; i++ )
		if(p_arr[i])
			for(j = i+i ; j< M ; j+= i )
				 p_arr[j] = 0 ;

}

void nod(int k ){
	int i  ,j  ,m  ;
	j =  k ;
	m = k/2 ;
  if(p_arr[k] ){
    si.push_back(_si( k ,  2 ));
    return ;

  }

	for(i =2 ;i <= m ;i++ ){
		if(k % i == 0){
		divv.pb( i);
		arr[i]++ ;
			k/= i ;
			while(1 ){
	//		printf("k - %d %d\n", k , i);
				if( k% i == 0){
					k /= i  ;
					arr[i]++;
				}
				else
					break ;
			}
		}
	}
	int mul = 1 ;
	rep(i , divv.size() ){
		k = arr[divv[i] ] +1 ;
		mul*= k ;
	}

	si.push_back(_si(j , mul ));
}

bool comp(_si a , _si b ){
  if(a.num  != b.num)  return a.num  < b.num  ;
  else  return a.var > b.var;

}

void build(){

int i , j ,k , tc , cs = 0 ;

  repi(i , 1000 ){
    rep(j ,1001 ){ arr[j] = 0 ; divv.clear();  }
    nod(i );

  }
  sort(si.begin() , si.end()  , comp);

//cout << "done \n";

	sf1(tc );
	while(tc--){

  sf1(k);

		printf("Case %d: %d\n" , ++cs , si[k-1].var);
	}
}

int main(){
int i ,j , k  ;
	seive();

  build();


	return 0 ;

}