আলোচনাঃ
চিত্র থেকে দেখতে পাচ্ছি, X base এর কোনো number কে 10 base(decimal number) এ convert করতে হলে ঐ base number এর power এর সাথে digit কে গুণ করতে হয়।
যেমনঃ
110 (In Binary) -> 2^2*1 + 2^1*1 + 2^0*0
-> 4 + 2 + 0
-> 6 (In Decimal)
অপরদিকে, 10 base থেকে কোনো number কে Y base এ নিতে হলে Y দিয়ে উক্ত number কে ভাগ করতে হয় যতক্ষণ না ভাগফল 0 হয়। যেমনঃ চিত্রে , 24 কে binary তে convert করা দেখানো হয়েছে। 24 এর binary = 11000. এখানে, binary value এর last digit হচ্ছে 0. আর এই জিনিসটাই আমাদের বের করা লাগবে। অর্থাত, একটা decimal number কে কোন কোন base এ convert করলে ঐ number এর শেষে অন্তত একটা 0 থাকবে।
উত্তরঃ
চিত্র (Image 2) থেকে দেখতে পাই, কোনো base value এর last digit = 0 হতে হলে, decimal value কে “যে base এ convert করতে চাই” তা দিয়ে নিঃশেষে ভাগ যেতে হবে। তার মানে ভাগশেষ 0 ( ভাগশেষ = লাল রং এর digit) হতে হবে। আর ভাগশেষ 0 হবে তখনই যখন ঐ decimal number কে তার divisor দিয়ে ভাগ করা হবে। কেবল N কে 1 দিয়ে ভাগ করা যাবে না কারণ প্রশ্নে আমাদের base limit দেয়া আছে “two to infinite”.তাই total divisor count থেকে 1 বাদ দিতে হবে কারণ, 1 সব number এর divisor.
C++ Code:
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=1e6;
vector<ll> prime;
bool vis[1000000];
ll divCount(ll &n){
ll ans=1;
for(ll i=0;i<prime.size() && prime[i]*prime[i]<=n;i++){
if(n%prime[i]==0){
ll cnt=1;
while(n%prime[i]==0){
cnt++;
n/=prime[i];
}
ans=ans*cnt;
}
}
if(n>1){
ans=ans*2;
}
return ans;
}
void sieve(){
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();
int i=1;
ll t,n;
scanf("%lld",&t);
while(t--){
scanf("%lld",&n);
printf("Case %d: %lld\n",i++,divCount(n)-1);
}
return 0;
}
Thanks a lot.
You are welcome.