ZeroJudge 解題筆記：k520. P8.幸運基數 (Base)

作者：王一哲
日期：2025年5月5日



ZeroJudge 題目連結：k520. P8.幸運基數 (Base)

解題想法

我在這題卡了很久，一直想不出比較有效率的寫法。由題目的敘述可知，如果要把10進位制的數字 $n$ 換成 $k$ 進位制表示，而且轉換後每個位數都是 $1$，一定會有的解是 $k = n-1$，轉換後為 $11$，如果 $k$ 越小，轉換後的位數越多。我有試著把 $3 \leq n \leq 1000$ 之中 $k \neq n-1$ 的數字列出來，但看不出規律。

(7, 2), (13, 3), (15, 2), (21, 4), (31, 2), (31, 5), (40, 3), (43, 6), (57, 7), (63, 2),
(73, 8), (85, 4), (91, 9), (111, 10), (121, 3), (127, 2), (133, 11), (156, 5), (157, 12), (183, 13), 
(211, 14), (241, 15), (255, 2), (259, 6), (273, 16), (307, 17), (341, 4), (343, 18), (364, 3), (381, 19),
(400, 7), (421, 20), (463, 21), (507, 22), (511, 2), (553, 23), (585, 8), (601, 24), (651, 25), (703, 26),
(757, 27), (781, 5), (813, 28), (820, 9), (871, 29), (931, 30), (993, 31)

後來想到，如果 $k$ 越小，轉換後的位數越多，那就先算出 2 進位制的位數，然後位置依序遞減到 2 為止，每次再用二分搜尋法，在 $low = 2, high = n-1$ 之間找解，雖然有很多次不必要的計算，但至少能正確地找到答案。

Python 程式碼

使用時間約為 33 ms，記憶體約為 3.4 MB，通過測試。

import sys, math

# 檢查以 base 為底，在指定位數 digit 的值與 num 的大小關係
def check(num, base, digit):
    power, total = 1, 0  # 目前的次方，加總
    for i in range(digit):  # 從個位數開始往左計算 
        total += power  # 更新 total
        power *= base  # 更新 power 為 base**(i+1)
        if total > num: return 1  # 如果 total 大於 num，回傳 1，跳出函式
    if total == num: return 0  # 如果最後 total 等於 num，回傳 0
    return -1  # 否則回傳 -1

for line in sys.stdin:
    n = int(line)  # 要找基底的數字 n
    ans = n-1  # 答案預設為 n-1
    digitmax = math.ceil(math.log(n, 2))  # 最多的位數
    for digit in range(digitmax, 1, -1):  # 依序檢查最多位數到 2 位數
        low, high = 2, n-1  # 下限 2，上限 n-1
        while low <= high:  # 當 low 小於等於 high，繼續執行
            mid = (high - low)//2 + low  # 取中間值
            state = check(n, mid, digit)  # 呼叫 check 檢查大小關係
            if state == 0:  # 找到解，更新 ans 為較小的值，降低 high
                ans = min(ans, mid); high = mid-1
            elif state == 1: high = mid-1 # mid 太大，降低 hight
            else: low = mid+1  # mid 太小，提高 low
    print(ans)  # 印出答案

改成先檢查 2，使用時間約為 30 ms，記憶體約為 3.4 MB，通過測試。

import sys, math

# 檢查以 base 為底，在指定位數 digit 的值與 num 的大小關係
def check(num, base, digit):
    power, total = 1, 0  # 目前的次方，加總
    for i in range(digit):  # 從個位數開始往左計算 
        total += power  # 更新 total
        power *= base  # 更新 power 為 base**(i+1)
        if total > num: return 1  # 如果 total 大於 num，回傳 1，跳出函式
    if total == num: return 0  # 如果最後 total 等於 num，回傳 0
    return -1  # 否則回傳 -1

for line in sys.stdin:
    n = int(line)  # 要找基底的數字 n
    ans = n-1  # 答案預設為 n-1
    digitmax = math.ceil(math.log(n, 2))  # 最多的位數
    if check(n, 2, digitmax) == 0:  # 如果 2 是解，一定是最小值，不需要檢查其它的數字
        ans = 2
    else:
        for digit in range(digitmax, 1, -1):  # 依序檢查最多位數到 2 位數
            low, high = 2, n-1  # 下限 2，上限 n-1
            while low <= high:  # 當 low 小於等於 high，繼續執行
                mid = (high - low)//2 + low  # 取中間值
                state = check(n, mid, digit)  # 呼叫 check 檢查大小關係
                if state == 0:  # 找到解，更新 ans 為較小的值，降低 high
                    ans = min(ans, mid); high = mid-1
                elif state == 1: high = mid-1 # mid 太大，降低 hight
                else: low = mid+1  # mid 太小，提高 low
    print(ans)  # 印出答案

C++ 程式碼

使用時間約為 2 ms，記憶體約為 140 kB，通過測試。可能是因為我先檢查了 2 是否為解，如果 2 不是解才檢查其它的數值，少了很多次運算，少存了一些東西，使用的記憶體反而特別少。

#include <cstdio>
#include <cmath>
#include <algorithm>
typedef long long LL;
using namespace std;

/* 檢查以 base 為底，在指定位數 digit 的值與 num 的大小關係 */
int check(LL num, LL base, LL digit) {
    LL power = 1, total = 0;  // 目前的次方，加總
    for(LL i=0; i<digit; i++) {  // 從個位數開始往左計算 
        total += power;  // 更新 total
        power *= base;  // 更新 power 為 base**(i+1)
        if (total > num) return 1;  // 如果 total 大於 num，回傳 1，跳出函式
    }
    if (total == num) return 0;  // 如果最後 total 等於 num，回傳 0
    return -1;  // 否則回傳 -1
}

int main() {
    LL n;  // 要找基底的數字 n
    while(scanf("%lld", &n) != EOF) {
        LL ans = n-1;  // 答案預設為 n-1
        int digitmax = ceil(log2(n));  // 最多的位數
        if (check(n, 2, digitmax) == 0) {
            ans = 2;
        } else {
            for(LL digit=digitmax; digit > 1; digit--) {  // 依序檢查最多位數到 2 位數
                LL low = 2, high = n-1;  // 下限 2，上限 n-1
                while(low <= high) {  // 當 low 小於等於 high，繼續執行
                    LL mid = (high - low)/2 + low;  // 取中間值
                    LL state = check(n, mid, digit);  // 呼叫 check 檢查大小關係
                    if (state == 0) {  // 找到解，更新 ans 為較小的值，降低 high
                        ans = min(ans, mid); high = mid-1;
                    } else if (state == 1) {  // mid 太大，降低 hight
                        high = mid-1;
                    } else {  // mid 太小，提高 low
                        low = mid+1;
                    }
                }
            }
        }
        printf("%lld\n", ans);  // 印出答案
    }
    return 0;
}