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の公式を使って余りを計算して解こうとしていたのの名残です。）

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;
}