如何检查大十进制数是否可以除以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;