題目
給你一個 N 進位的 R，找出使 R 能被 (N-1) 整除的最小 N。
7
13
2y
arping8
5
such number is impossible!
56解法
【觀念1】N 進位的 abc = a × N^2 + b × N^1 + c。
舉例：3 進位的 123 = 1 × 3^2 + 2 × 3^1 + 3 = 18。
【觀念2】當你在 R 中看到 x 時，代表一定是 (x+1) 進位以上。
舉例：
10 進位：只會使用 0 到 9 ➡️ 當你看到 10 時，代表一定是 11 進位以上。
2 進位：只會使用 0 到 1 ➡️ 當你看到 2 時，代表一定是 3 進位以上。
注意：R 可能很大（當 N = 62 時，62 的 6 次方會超過 int），要用 long long。
#include <iostream>
#include <string>
#include <cmath>
using namespace std;
int main(){
string s;
string list = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz";
while(cin >> s){
int base = 2, ans = -1;
for(int i=0; i<s.length(); i++){
base = max(base, (int)list.find(s[i]) + 1);
}
for(int N=base; N<=62; N++){
long long R = 0;
for(int i=0; i<s.length(); i++){
R += list.find(s[i]) * pow(N, s.length() - 1 - i);
}
if(R % (N - 1) == 0){
ans = N;
break;
}
}
if(ans != -1) cout << ans << '\n';
else cout << "such number is impossible!\n";
}
}👉 回到：【CPE大學程式能力檢定】目錄
