C++ 中检查大数是否能被 13 整除

在这里，我们将了解如何检查一个数是否能被 13 整除。在这种情况下，数字非常大。因此，我们将数字作为字符串输入。

如果数字满足以下情况，则该数字可以被 13 整除：

  • 当且仅当我们得到交替和（即从右到左交替加减三位数的块）可以被 13 整除时，一个数才能被 13 整除。例如，2911285 可以被 13 整除，因为大小为 3 的块的交替和为 2 – 911 + 285 = -650，该和可以被 13 整除。
  • 当且仅当该数是由将最后一位数字乘以 4 加到其余数字所形成的数也可以被 13 整除时，该数才能被 13 整除。例如，考虑 2353。应用上述规则，我们得到 235 + 3*4 = 247。在下一次迭代中，24 + 7*4 = 52。由于 52 可以被 13 整除，因此给定数字可以被 13 整除。

示例

 在线演示

#include <bits/stdc++.h>
using namespace std;
bool isDiv13(string num){
   int length = num.size();
   if (length == 1 && num[0] == '0')
      return true;
   if (length % 3 == 1) { //when length is not divisible by 3, remainder is 1
      num +="00";
      length += 2;
   } else if (length % 3 == 2){ //when length is not divisible by 3, remainder is 2
      num += "0";
      length += 1;
   }
   int sum = 0, p = 1;
   for (int i = length - 1; i >= 0; i--) {
      int set = 0;
      set += (num[i--] - '0');
      set += (num[i--] - '0') * 10;
      set += (num[i] - '0') * 100;
      sum = sum + set * p;
      p *= (-1);
   }
   sum = abs(sum);
   return (sum % 13 == 0);
}
int main() {
   string num = "83959092724";
   if(isDiv13(num)){
      cout << "Divisible";
   } else {
      cout << "Not Divisible";
   }
}

输出

Divisible

更新于: 2019年10月22日

287 次浏览

开启您的 职业生涯

通过完成课程获得认证

开始学习
广告