আলোচনাঃ
প্রশ্নে দেয়া সংখ্যা টা নিয়েই বুঝা যাক,
67500 কে prime factorization করলে হয় 2^2 + 3^3 + 5^4
এখানে 2 এর উপর power 2, 3 এর উপর power 3 আবার 5 এর উপর power 4. তার মানে power জোড় এমন সংখ্যা আছে 2টা। তারা হচ্ছে 2,5.
অন্যদিকে power বিজোড় এমন সংখ্যা আছে ১ টা আর তা হলো ৩। তাহলে দেখা যাচ্ছে power even এমন নম্বর 67500 এর prime factorization এ বেশি আছে। তাই 67500 একটা psycho number . বিপরীত ঘটনা ঘটলে সেটা হবে ordinary number.
উত্তরঃ
এখানে লক্ষণীয় বিষয় হচ্ছে time limit অনেক কম 0.5s . আর এখানে যেহেতু prime factor বের করা লাগবে তাই আমরা sieve চালিয়ে
Prime number আগেই pre-calculate করে রাখতে পারি। এতে আমাদের O(Nlog(logN)) টাইম লাগবে। অন্যদিকে আমাদের যেহেতু prime factor এর power বের করা লাগবে তাই আমাদের দেখা দরকার prime factor দিয়ে N কতবার ভাগ যায়। যদি prime factor দিয়ে N জোড় সংখ্যক বার ভাগ যায় তাহলে even কে 1 করে বাড়াবো। তা নাহলে odd কে এক করে বাড়াবো।
কিন্তু যদি এমন হয় যে, N কে prime factor দিয়ে ভাগ করার পরেও N>1 কিংবা একবার ও ভাগ করা গেলো না , তখন কাকে বাড়াবো?
আসলে যদি N একটা prime number হয় তখনই কেবল এই scenario সম্ভব। কারণ prime number কে তার থেকে ছোট কোনো prime number দিয়ে ভাগ করা যাবে না। আর prime number এর power always odd হবে। 2 আর 17 নিয়ে নিয়ে চিন্তা করলেই ব্যাপারটা বুঝা যাবে।
C++ Code:
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define MOD 100
const ll N=1e7;
vector<ll> prime,factor;
bool vis[N];
ll divCount(ll n){ //O(sqrt(n))
ll ans=1,even=0,odd=0;
if(n==0 || n==1) return 0;
for(ll i=0;i<prime.size() && prime[i]*prime[i]<=n;i++){
ll cn=0;
if(n%prime[i]==0){
while(n%prime[i]==0){
cn++;
n/=prime[i];
}
if(cn%2==0) even++;
else odd++;
}
}
if(n>1){
odd++;
}
if(even>odd) return 1;
return 0;
}
void sieve(){ //O(Nlog(logN))
for(ll i=3;i*i<=N;i+=2){
if(vis[i]==0){
for(ll j=i*i;j<=N;j+=2*i){
vis[j]=1;
}
}
}
prime.push_back(2);
for(ll i=3;i<=N;i+=2){
if(vis[i]==0) prime.push_back(i);
}
}
int main(){
sieve();
ll t,n;
//cin>>t;
scanf("%lld",&t);
while(t--){
scanf("%lld",&n);
if(divCount(n)) printf("Psycho Number\n");
else printf("Ordinary Number\n");
}
}
// Time Complexity : O(Nlog(logN)) + T*O(sqrt(n))