給定十進位制表示的數字 N，找到其在任何基數（基數 b）下的位數。

---

問題陳述包括在任何基數 b 數制中表示 N 時找到其位數。最初，N 以基數 10 數制給出。

在問題中，我們將獲得輸入中的正整數 N，它將以基數 10 數製表示，以及大於 1 的正整數 b。我們的任務是找到 N 在基數 b 數制中表示時的位數。

任何以任何基數表示的數字，從右起每一位都表示該基數的冪的倍數，從 0 開始。

例如，當我們將 15 表示為基數 3 時。

它被表示為 120，即 $\mathrm{0*3^{0}+2*3^{1}+1*3^{2}=0+6+9=15}$

讓我們透過以下示例更好地理解問題。

輸入

N=16   b=5

輸出

2

解釋 - 在這裡，我們以基數 10 表示的形式給出 N，即 16。我們需要計算 N 在基數 5 中表示時的位數。

16 在基數 5 中的表示為 31，即 $\mathrm{1*5^{0}+3*5^{1}=1+15=16}$

16 在基數 5 中表示的位數為 2（即 31），這是我們所需的輸出。

輸入

N= 22    b=3

輸出

3

解釋 - 以基數 10 數製表示的 N 的值為 22，並且我們給定的基數等於 3。22 在基數 3 中的表示為 211，即 $\mathrm{1*3^{0}+1*3^{1}+2*3^{2}=1+3+18=22}$

因此，22 在基數 3 中表示的位數為 3，這是我們所需的輸出。

讓我們探索從樸素到高效解決方案的不同方法來計算任何數字 N 在基數 b 中表示的位數。

方法 1（樸素方法）

該解決方案的樸素方法將是將 N 表示為基數 b 數制並計算位數。

為了找到 N 在基數 b 中表示的位數，我們將建立一個函式。我們將初始化一個變數來儲存位數，並透過將 N 除以 b 來更新 N，直到 N 大於 0，並在每次迭代中增加位數。透過這種方式，我們可以計算 N 在基數 b 中表示的位數。

這可以更好地解釋為，要將任何數字表示為任何基數，我們取該數字對基數的模，它表示從右起每一位，並透過將該數字除以基數值來更新該數字，並重復此過程，直到該數字大於 0。

在 C++ 中實現該方法的步驟

• 我們將建立一個函式來計算 N 在基數 b 中表示的位數。

• 初始化一個變數來儲存位數。

• 在 while 迴圈中迭代，直到 N 大於 0。

• 在每次迭代中，透過將 N 除以 b 來更新 N，並將計數增加 1，因為要找到表示中的下一個左邊的位，我們取 N 對 b 的模，並使用更新後的 N。

• 當 N 等於零時返回變數，這將是 N 在基數 b 數制中表示的位數。

示例

//C++ code to find the number of digits of N when represented in base b

#include <bits/stdc++.h>

using namespace std;

//function to calculate the number of digits of N in base b
int digits(long long int N, long long int b){
    //to store the number of digits of N in base b
    int a=0;
    
    //iterating to calculate the number of digits
    while(N>0){
        N = N/b; //update N by dividing it with b to find the next digit
        a++; //increase the count by 1 
    }
    
    return a;
}

int main()
{
    long long int N,b; //for taking input values
    
    N=58734;
    b=4;
    //calling the function
    cout<<"No. of digits of "<<N<<" in base-"<<b<<" :"<<digits(N,b)<<endl;

    return 0;
}

輸出

No. of digits of 58734 in base-4 :8

時間複雜度：O(log N)，因為我們在 while 迴圈中迭代，直到 N 大於 0，並不斷將 N 除以基數值。

空間複雜度：O(1)，因為沒有佔用額外的空間來查詢位數。

方法 2（高效方法）

我們可以使用數學中的對數函式的概念以更有效的方式解決問題。

N 在基數 b 中表示的位數與數字 N 和基數 b 之間存在數學關係。N 在基數 b 中表示的位數為（1 + N 以 b 為底的對數值）。

讓我們透過下面的插圖更好地理解這種關係。

假設，N 在基數b中表示的位數為a。

N 的值將落在範圍 $\mathrm{b^{a−1}<=N<b^{a}}$ 內，因為每一位都表示從 0 開始的基數的冪。因此，如果 N 有 a 位，則 N 的值必須等於或大於 $\mathrm{b^{a−1}}$（因為 a 從 0 開始）並且必須小於 $\mathrm{b^{a}}$（這是 b 的下一個冪）。

在等式兩邊取以 b 為底的對數，我們得到

$$\mathrm{(a−1)*\log_{b}b<=\log_{b}N}$$

任何數字以自身為底的對數始終為 1。因此，最終表示式將為

$\mathrm{a<=\frac{\log\:N}{\log\:b}+1}$，因為 $\mathrm{\log_{b}N}$ 可以寫成 $\mathrm{\frac{\log\:N}{\log\:b}}$

我們將使用上述公式在使用 C++ 中的 log() 函式的恆定執行時內計算 N 在基數 b 中的位數，該函式返回等於傳遞的引數的自然對數的值。

在 C++ 中實現該方法的步驟

• 建立一個函式來計算 N 在基數 b 中的位數。

• 初始化一個變數來儲存位數。

• 使用匯出的公式，我們將計算位數。log() 函式可能會返回十進位制值，因此我們將使用 floor() 函式來獲取小於或等於 log() 函式返回值的最大整數，並確保 a 始終小於或等於 $\mathrm{\frac{\log\:N}{\log\:b}}$

• 返回使用公式計算的位數，這將是我們的輸出。

示例

//C++ code to find the number of digits of N when represented in base b

#include <bits/stdc++.h>

using namespace std;

//function to calculate number of digits
int digits(long long int N, long long int b){
    //to store the number of digits of N in base b
    int a=0;
    
    a = floor( log(N) / log(b) ) + 1; //using the formula to calculate number of digits
    
    return a; //return number of digits
}

int main()
{
    long long int N,b; //for taking input values
    
    N=1e15; //storing 10^15 in N
    b=9;
    //calling the function
    cout<<"No. of digits of "<<N<<" in base-"<<b<<" :"<<digits(N,b)<<endl;

    return 0;
}

輸出

No. of digits of 1000000000000000 in base-9 :16

時間複雜度 - O(1)，因為 log() 函式在恆定時間內返回該值

空間複雜度 - O(1)，因為沒有佔用額外的空間。

結論

本文討論了在任何基數 b（將在輸入中給出）中表示 N 時查詢 N 的位數的概念。我們使用從樸素方法到使用 C++ 中對數函式概念的高效解決方案解決了該問題，並在恆定執行時和空間內實現了該問題。

希望您在閱讀本文後能夠理解問題以及解決問題的方法。