描述

在娱乐数学里,纯位数为一由相同位元重复而组成的自然数,通常指在十进位里。亦可指其他的进位,如156在五进位内即为纯位数(1111)。 例如11、222、4444、77777及999999。所有的纯位数都是回文数,以及循环单位的倍数。

输入

一个正整数 N (0 < N < 10^8)

输出

使 N 为纯位数的最小进位 K

思路

分别考虑1位、2位、3位,1位直接给出,针对2位对位元剪枝,针对3位对进制剪枝。

代码

int getRadix(int c) {
    int i, a, b, mod;
    // for one digit
    int ret = c + 1;
    if (c <= 2) {
        return c + 1;
    }
    for (i = 2; i <= sqrt(c) + 1; i++) {
        // for more digit
        b = i;
        int t = c;
        int a = t % b;
        if (a != 0) {
                while (t > 0 && t != a) {
                    t = t / b;
                    mod = t % b;
                    if (mod != a) {
                        break;
                    }
                }
                if (t == a) {
                    return b;
                }
        }
        // for double digit
        a = i - 1;
        if (c % a == 0) {
             ret = c / a - 1;
        }
    }
    return ret;
}