Blog

Problem link

আলোচনাঃ
চিত্র থেকে দেখতে পাচ্ছি, 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;
}