algorithm - 如何在不转换的情况下检查不以 10 为基数的数字的整除性？

Question

假设我有一个以 3 为底数的数字 1211。我如何检查这个数字是否可以被 2 整除而不将其转换回以 10 为底数？

更新
原题出自TopCoder
数字 3 和 9 共享一个有趣的属性。如果你取 3 的任何倍数并将其数字相加，你将得到另一个 3 的倍数。例如，118*3 = 354 和 3+5+4 = 12，它是 3 的倍数。同样，如果你取任何倍数9 和它的数字相加，你得到另一个 9 的倍数。例如，75*9 = 675 和 6+7+5 = 18，它是 9 的倍数。调用这个属性感兴趣的任何数字，除了0 和 1，对于它们来说，这个属性是微不足道的。在一个碱基中有趣的数字在另一个碱基中不一定有趣。例如，3 以 10 为基数很有趣，但以 5 为基数则无趣。给定一个 int 基数，您的任务是按递增顺序返回该基数的所有有趣数字。要确定某个特定数字是否有趣，您无需考虑该数字的所有倍数。可以肯定的是，如果该属性适用于少于四位数的数字的所有倍数，那么它也适用于位数更多的倍数。例如，以 10 为底，您不需要考虑任何大于 999 的倍数。
注意事项
- 当基数大于 10 时，数字可能具有大于 9 的数值。由于默认情况下整数以 10 为基数显示，因此当此类数字在屏幕上显示为多于一位小数时，请不要 panic 。例如，以 16 为基数的有趣数字之一是 15。
约束
- 基数在 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 以三为底，那么你可以把它写成

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

其中 a0、a1、...、an 是三进制表示中的数字。

要查看数字是否可以被 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)

换句话说，如果你把三进制表示的数字加起来，得到这个值可以被二整除，那么这个数本身也一定是可以被二整除的。更酷的是，由于三进制数字只有0、1、2，这相当于在问三进制表示中1的个数是否为偶数!

不过，更一般地说，如果你有一个基数为 m 的数字，那么该数字可以被 m - 1 整除，当且仅当数字之和可以被 m 整除。这就是为什么您可以通过对数字求和并查看该值是否可以被 9 整除来检查以 10 为底的数字是否可以被 9 整除。