আলোচনাঃ
প্রশ্নে বলা হয়েছে, 1-1000 পর্যন্ত নম্বর sort করা লাগবে আর sort করার 2টা শর্ত
দেয়া আছে।তা হলো-
1টা নম্বর যদি x হয় এবং অপরটি যদি y হয়,তাহলে
1) x কে y এর আগে বসাতে হবে, যদি x এর divisor সংখ্যা y এর divisor
সংখ্যা থেকে কম হয়।
2) x কে y এর আগে বসাতে হবে, যদি x এর divisor সংখ্যা ও y এর divisor
সংখ্যা সমান হয় এবং x>y হয়।
উত্তরঃ
একটা array তো আমরা sort() function ব্যবহার করেই sort করে ফেলতে
পারবো কেবল শর্ত অনুযায়ী একটা বাড়তি compare function লিখা লাগবে।
আর যেহেতু sort করতে হবে divisor এর সংখ্যার ভিত্তিতে তাই আমাদের divisor
count করার জন্য একটা function লিখা লাগবে। আর divisor count করতে
হলে prime number দিয়ে আমরা prime factorization করে গণনা করতে
পারি । আর যেহেতু prime number লাগবে তাই sieve চালিয়ে prime number
আগেই pre-calculate করে রাখতে পারি।
আর compare function টা কিভাবে লিখব? শর্তে যা বলা আছে সেগুলোই
condition এ copy করে দিব। যদি condition true হয় তাহলে true return
করব। তা নাহলে false return করব।
বিঃদ্রঃ যেহেতু T এবং N খুব ছোট তাই আমরা সাধারণ brute force দিয়েও solve
করতে পারবো:)
C++ Code:
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1000;
#define mp make_pair
vector<int> prime;
vector<pair<int,int> > divisor;
bool vis[N];
bool cmp(pair<int,int> x, pair<int,int> y){ // pair<number(n),divisor>
if(x.second<y.second){
return 1;
}
else if(x.second==y.second && x.first>y.first){
return 1;
}
else return 0;
}
void divCount(int n){ //O(sqrt(N))
int temp=n;
int ans=1;
for(int i=0;i<prime.size() && prime[i]*prime[i]<=n;i++){
int cn=1;
if(n%prime[i]==0){
while(n%prime[i]==0){
cn++;
n/=prime[i];
}
ans=ans*cn;
}
}
if(n>1){
ans=ans*2;
}
divisor.push_back(mp(temp,ans));
}
void sieve(){
for(int i=3;i*i<=N;i+=2){
if(vis[i]==0){
for(int j=i*i;j<=N;j+=2*i){
vis[j]=1;
}
}
}
prime.push_back(2);
for(int i=3;i<=N;i+=2){
if(vis[i]==0) prime.push_back(i);
}
}
int main(){
sieve(); //O(Nlog(logN))
int t,n;
for(int i=1;i<=1000;i++){
divCount(i); // N*O(sqrt(N))
}
sort(divisor.begin(),divisor.end(),cmp); // O(NlogN)
scanf("%d",&t);
for(int i=1;i<=t;i++){
scanf("%d",&n);
printf("Case %d: %d\n",i,divisor[n-1].first); // O(1)
}
}