如何检查大十进制数是否可以除以 2^x 或 5^x

Question

我有一个很大的十进制数 N（最多 100.000 位），我需要检查 N 是否可以除以 2^X 或 5^X ( 0 < X < 5 ).

bignumber % (2^x) == 0

我能得到小费吗？我不知道。

Answer 1

检查由最后 x 位数字组成的数字。如果它可以除以 2^x，那么所有数字也可以。同样关于 5^x.

原因是最后有 x 个零的十进制数总是可以除以 2^x 或 5^x，因为它可以除以 10^x。所以，我们可以忘记开始数字，只检查最后 x 个。

检查整除性使用

char* number; // here the source number is put

strcopy(ending, &number[strlen(number) - x]);
long CheckedNumber = atoi(ending);

long NewCheckedNumber;
int i=0;
while (i<x){
  NewCheckedNumber = CheckedNumber / 5;
  if ( NewCheckedNumber * 5 != CheckedNumber ) return 0;
  CheckedNumber = NewCheckedNumber;
  i++;
}
return 1;

Answer 2

如果 0 < x < 5 => 很简单:)

X 绝对是一个整数。 => X = 1,2,3,4

您只需检查每个案例。例如X = 4 => 5^4 = 625

你必须检查是否 Bignumber %625 == 0

你知道 10000 % 625 == 0 => 如果这些 4 数字除以 625，只需检查最后一个 4 => 大数字除以 625。

你还好吗？

Answer 3

https://www.mathsisfun.com/divisibility-rules.html

一个数是否可以整除，应该列出来。它适用于所有数字，无论数字有多大。

Answer 4

您面临两个问题：

如何存储大数。
如何计算该数字的除法并得到余数。

在计算机上存储如此大的数字是一项挑战。但是任何数字都可以表示为多项式。

ex: 10235
base 10 -->  10235 = f(10) = 1x10^5 + 0x10^4 + 2x10^3 + 3x10^2 + 3x10 + 5
base 16 --> 0x37FB = g(16) = 2x16^3 + 7x16^2 + 15x16^1 + 11

利用这一概念，人们可以轻松地使用多项式加法、减法、乘法和除法来计算非常大的值，而不会损失精度。只需要设置多项式的系数，使它们在打印数字时都具有相同的符号。

要打印以 N 为底到 10 为底的数字存储，必须计算 f 以便 f(10) = g(N)。

这个概念可以用大于 10 的数字进行优化，以减少计算时间，但您需要记住，31 位 x 32 位（乘法需要 64。负系数或大于基数的系数可以使用我们在手动进行算术运算时经常使用的相同 carry/borrow 技术来减少。

您可以开发自己的多项式库，处理循环和数学，或者使用开源库，例如 GMP。

关于多项式除法余数的一些信息：

https://en.wikipedia.org/wiki/Polynomial_remainder_theorem

我会选择使用 GMP。

如何检查大十进制数是否可以除以 2^x 或 5^x

How to check if a big decimal number can be divided by 2^x or 5^x

algorithm

division

modulus