如何在不转换的情况下检查不在10的数字的可分性？

Question

假设我有一些基数3,1211.我怎么能检查这个数字是否可被2整除而不将其转换回基数10？

更新
原始问题来自TopCoder
数字3和9共享一个有趣的属性.如果取3的任意倍数并加上其数字,则得到3的另一个倍数.例如,118*3 = 354和3 + 5 + 4 = 12,这是3的倍数.同样,如果你取任何倍数9和9的总和,你得到9的另一个倍数.例如,75*9 = 675和6 + 7 + 5 = 18,这是9的倍数.调用此属性有趣的任何数字,除了0和1,财产保持平凡.在一个基础中感兴趣的数字在另一个基础中不一定有趣.例如,3在基数10中很有趣但在基数5中不感兴趣.给定一个int基础,你的任务是按递增顺序返回该基数的所有有趣数字.要确定某个特定数字是否有趣,您无需考虑该数字的所有倍数.您可以确定,如果该属性适用于少于四位数的所有数字的倍数,则它也适用于具有更多数字的倍数.例如,在基数10中,您不需要考虑任何大于999的倍数.
注意
- 当base大于10时,数字的数值可能大于9.因为默认情况下整数显示在基数10中,所以不要当这些数字在屏幕上出现超过一位十进制数字时会发出警报.例如,基数16中的一个有趣数字是15.
约束
- 基数在3到30之间,包括3和30.

这是我的解决方案:

class InterestingDigits {
public:
    vector<int> digits( int base ) {
        vector<int> temp;
        for( int i = 2; i <= base; ++i )
            if( base % i == 1 )
                temp.push_back( i );
        return temp;
    }
};

诀窍在这里得到了很好的解释:https://math.stackexchange.com/questions/17242/how-does-base-of-a-number-relate-to-modulos-of-its-each-individual-digit

谢谢,
陈

Answer 1

如果您的数字k在基数为3,那么您可以将其编写为

k = a0 3^n + a1 3^{n-1} + a2 3^{n-2} + ... + an 3^0

其中a0,a1,...,an是base-three表示中的数字.

要查看该数字是否可被2整除,您会对模数为2的数字是否等于零感兴趣.那么,k mod 2由下式给出

k mod 2 = (a0 3^n + a1 3^{n-1} + a2 3^{n-2} + ... + an 3^0) mod 2
        = (a0 3^n) mod 2 + (a1 3^{n-1}) mod 2 + ... + an (3^0) mod 2
        = (a0 mod 2) (3^n mod 2) + ... + (an mod 2) (3^0 mod 2)

这里的诀窍是3 ^ i = 1(mod 2),所以这个表达式是

k mod 2 = (a0 mod 2) + (a1 mod 2) + ... + (an mod 2)

换句话说,如果你总结三元表示的数字并得到该值可以被2整除,那么数字本身必须可以被2整除.为了使它更酷,因为唯一的三元数字是0,1和2,这相当于询问三元表示中的1的数量是否是偶数!

但更一般地说,如果你有一个以m为基数的数字,那么这个数字可以被m - 1整除,如果这些数字的总和可以被m整除.这就是为什么你可以通过对数字求和并查看该值是否可被9整除来检查基数10中的数字是否可被9整除.

Answer 2

您始终可以为任何基数和任何除数构建有限自动机：

n通常，要计算基数中的一串数字的值，b 您需要迭代这些数字并执行以下操作

n = (n * b) + d

对于每个数字d。

现在，如果您对整除性感兴趣，您可以执行以下取模操作m：

n = ((n * b) + d) % m

这里n最多可以取m不同的值。d将这些视为有限自动机的状态，并根据该公式计算取决于数字的转换。接受状态是余数为 的状态0。

针对您的具体情况，我们有

n == 0, d == 0: n = ((0 * 3) + 0) % 2 = 0
n == 0, d == 1: n = ((0 * 3) + 1) % 2 = 1
n == 0, d == 2: n = ((0 * 3) + 2) % 2 = 0
n == 1, d == 0: n = ((1 * 3) + 0) % 2 = 1
n == 1, d == 1: n = ((1 * 3) + 1) % 2 = 0
n == 1, d == 2: n = ((1 * 3) + 2) % 2 = 1

这表明您可以只对数字 1 模 2 求和并忽略任何数字 0 或 2。