如何在不转换的情况下检查非 10 基数的整除性？

发布于 2024-10-13 14:22:12 字数 1272 浏览 3 评论 0原文

假设我有一个以 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 为基数显示，因此当此类数字在屏幕上显示为多于一位十进制数字时，请不要惊慌。例如，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-数字

谢谢，
陈

原文

Let's say I have a number of base 3, 1211. How could I check this number is divisible by 2 without converting it back to base 10?

Update
The original problem is from TopCoder
The digits 3 and 9 share an interesting property. If you take any multiple of 3 and sum its digits, you get another multiple of 3. For example, 118*3 = 354 and 3+5+4 = 12, which is a multiple of 3. Similarly, if you take any multiple of 9 and sum its digits, you get another multiple of 9. For example, 75*9 = 675 and 6+7+5 = 18, which is a multiple of 9. Call any digit for which this property holds interesting, except for 0 and 1, for which the property holds trivially.
A digit that is interesting in one base is not necessarily interesting in another base. For example, 3 is interesting in base 10 but uninteresting in base 5. Given an int base, your task is to return all the interesting digits for that base in increasing order. To determine whether a particular digit is interesting or not, you need not consider all multiples of the digit. You can be certain that, if the property holds for all multiples of the digit with fewer than four digits, then it also holds for multiples with more digits. For example, in base 10, you would not need to consider any multiples greater than 999.
Notes
- When base is greater than 10, digits may have a numeric value greater than 9. Because integers are displayed in base 10 by default, do not be alarmed when such digits appear on your screen as more than one decimal digit. For example, one of the interesting digits in base 16 is 15.
Constraints
- base is between 3 and 30, inclusive.

This is my solution:

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

The trick was well explained here : https://math.stackexchange.com/questions/17242/how-does-base-of-a-number-relate-to-modulos-of-its-each-individual-digit

Thanks,
Chan

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

自由如风 2024-10-20 14:22:12

如果您的数字 k 以三为基数，则可以将其写为

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

其中 a0、a1、...、an 是三基数表示形式中的数字。

要查看该数字是否能被 2 整除，您需要了解该数字模 2 是否等于 0。好吧，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 整除。

If your number k is in base three, then you can write it as

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

where a0, a1, ..., an are the digits in the base-three representation.

To see if the number is divisible by two, you're interested in whether the number, modulo 2, is equal to zero. Well, k mod 2 is given by

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)

The trick here is that 3^i = 1 (mod 2), so this expression is

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

In other words, if you sum up the digits of the ternary representation and get that this value is divisible by two, then the number itself must be divisible by two. To make this even cooler, since the only ternary digits are 0, 1, and 2, this is equivalent to asking whether the number of 1s in the ternary representation is even!

More generally, though, if you have a number in base m, then that number is divisible by m - 1 iff the sum of the digits is divisible by m. This is why you can check if a number in base 10 is divisible by 9 by summing the digits and seeing if that value is divisible by nine.

回复收藏 0 原文

这个俗人 2024-10-20 14:22:12

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

通常计算基数 b 中的数字字符串的值 n
您迭代这些数字并对

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。

You can always build a finite automaton for any base and any divisor:

Normally to compute the value n of a string of digits in base b
you iterate over the digits and do

n = (n * b) + d

for each digit d.

Now if you are interested in divisibility you do this modulo m instead:

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

Here n can take at most m different values. Take these as states of a finite automaton, and compute the transitions depending on the digit d according to that formula. The accepting state is the one where the remainder is 0.

For your specific case we have

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

which shows that you can just sum the digits 1 modulo 2 and ignore any digits 0 or 2.

回复收藏 0 原文

∞梦里开花 2024-10-20 14:22:12

将所有数字加在一起（或者甚至只计算个数） - 如果答案是奇数，则数字是奇数；如果是偶数，则数字是偶数。

这是如何运作的？数字中的每个数字贡献 0、1 或 2 次（1、3、9、27，...）。 0 或 2 添加偶数，因此对整个数字的奇数/偶数（奇偶性）没有影响。 1 加上 3 的幂之一，这始终是奇数，因此翻转奇偶校验）。我们从 0（偶数）开始。因此，通过计算翻转次数是奇数还是偶数，我们可以判断数字本身是否是奇数或偶数。

回复收藏 0 原文

你在看孤独的风景 2024-10-20 14:22:12

我不确定在哪种 CPU 上您有一个以 3 为基数的数字，但执行此操作的正常方法是执行模数/余数运算。

if (n % 2 == 0) {
    // divisible by 2, so even
} else {
    // odd
}

如何实现模数运算符取决于您存储 3 进制数字的方式。最简单的编码可能是实现普通的纸笔长除法，并从中得到余数。

    0 2 2 0
    _______
2 ⟌ 1 2 1 1 
    0
    ---
    1 2
    1 1
    -----
      1 1
      1 1
      -----
        0 1 <--- remainder = 1 (so odd)

（无论基数如何，这都有效，正如其他人提到的，基数 3 有“技巧”）

I'm not sure on what CPU you have a number in base-3, but the normal way to do this is to perform a modulus/remainder operation.

if (n % 2 == 0) {
    // divisible by 2, so even
} else {
    // odd
}

How to implement the modulus operator is going to depend on how you're storing your base-3 number. The simplest to code will probably be to implement normal pencil-and-paper long division, and get the remainder from that.

    0 2 2 0
    _______
2 ⟌ 1 2 1 1 
    0
    ---
    1 2
    1 1
    -----
      1 1
      1 1
      -----
        0 1 <--- remainder = 1 (so odd)

(This works regardless of base, there are "tricks" for base-3 as others have mentioned)

回复收藏 0 原文

银河中√捞星星 2024-10-20 14:22:12

与以 10 为基数相同，例如：
1. 找到 2 的倍数 <= 1211，即 1210（请参阅下面如何实现它）
2. 1211 减去 1210，得到 1
3. 1 是 < 10，因此 1211 不能被 2 整除

如何获得 1210：
1. 2 开头
2. 2 + 2 = 11
3. 11 + 2 = 20
4. 20 + 2 = 22
5. 22 + 2 = 101
6. 101 + 2 = 110
7. 110 + 2 = 112
8. 112 + 2 = 121
9. 121 + 2 = 200
10. 200 + 2 = 202
... // 重复直到获得最大数字 <= 1211
它与基数 10 基本相同，只是向上舍入发生在 3 而不是 10。