n進数表記の数を(n-1)で割れるかどうか

面白い問題があったので、紹介。

http://poj.org/problem?id=1152

　n進数表記の数値を(n-1)で割り切れるかどうかは、すべての桁の数値を足した数が(n-1)で割れるかどうかを調べればいいです。例えば、10進数表記の111111111、45、1233、123453は桁の合計値が9で割れるので9の倍数です。

　n進数表記のm桁の数 A = A_(m-1).. A_2 A_1 A_0について考えます。つまり、

A = A_(m-1) * n^(m-1) + ... A_2 * n^(2) + A_1 * n^(1) + A_0

です。 n = 1 (mod (n-1))なので、

A = A_(m-1) + ... + A_2 + A_1 + A_0 (mod (n-1))

です。

ということで、Aの各桁の合計値を出してそれが(n-1)で割れるかどうかをみればOKです。

　C++のスパゲッティなソースを張っておきます。（dividable()の中で毎回合計値計算してるのは無駄ですね。。最初まじめにHormerの公式を使って余りを計算して解こうとしていたのの名残です。）

view plainprint?

1. int num[128];  
2.   
3. bool dividable(int k, const string &str) {  
4.     int len = str.length();  
5.     int digsum = 0;  
6.     REP(i, len) digsum += num[(int)str[i]];  
7.   
8.     return digsum % (k-1) == 0;  
9. }  
10.   
11. int main() {  
12.     string str;  
13.   
14.     for (int i = '0'; i <= '9'; i++) num[i] = i - '0';  
15.     for (int i = 'A'; i <= 'Z'; i++) num[i] = i - 'A' + 10;  
16.     for (int i = 'a'; i <= 'z'; i++) num[i] = i - 'a' + 36;  
17.   
18.     while (cin >> str) {  
19.         int len = str.length();  
20.         int base = 0;  
21.         REP(i, len) base = max(base, num[(int)str[i]]);  
22.         base = max(2, base+1);  
23.   
24.         int k;  
25.         for (k = base; k <= 62; k++)  
26.             if (dividable(k, str))  
27.                 break;  
28.   
29.         if (k <= 62) cout << k << endl;  
30.         else cout << "such number is impossible!" << endl;  
31.     }  
32.   
33.     return 0;  
34. }  

int num[128];

bool dividable(int k, const string &str) {
    int len = str.length();
    int digsum = 0;
    REP(i, len) digsum += num[(int)str[i]];

    return digsum % (k-1) == 0;
}

int main() {
    string str;

    for (int i = '0'; i <= '9'; i++) num[i] = i - '0';
    for (int i = 'A'; i <= 'Z'; i++) num[i] = i - 'A' + 10;
    for (int i = 'a'; i <= 'z'; i++) num[i] = i - 'a' + 36;

    while (cin >> str) {
        int len = str.length();
        int base = 0;
        REP(i, len) base = max(base, num[(int)str[i]]);
        base = max(2, base+1);

        int k;
        for (k = base; k <= 62; k++)
            if (dividable(k, str))
                break;

        if (k <= 62) cout << k << endl;
        else cout << "such number is impossible!" << endl;
    }

    return 0;
}