Sau đây chúng ta sẽ xem cách kiểm tra một số có chia hết cho 13 hay không. Trong trường hợp này số lượng là rất lớn. Vì vậy, chúng tôi đặt số dưới dạng chuỗi.
Một số sẽ chia hết cho 13, nếu số đó thỏa mãn các trường hợp sau -
- Một số chia hết cho 13 nếu và chỉ khi chúng ta nhận được tổng xen kẽ, tức là cộng và trừ các khối của ba số từ phải sang trái một cách xen kẽ thì chia hết cho 13. Ví dụ:2911285 chia hết cho 13 vì tổng xen kẽ của khối có kích thước 3 là 2 - 911 + 285 =-650 chia hết cho 13.
- Một số chia hết cho 13 nếu và chỉ khi số đó được tạo thành bằng cách thêm chữ số tận cùng nhân với 4 để còn lại cũng chia hết cho 13. Ví dụ, xét 2353. Áp dụng quy tắc trên, ta được 235 + 3 * 4 =247. Trong lần lặp tiếp theo, 24 + 7 * 4 =52. Vì 52 chia hết cho 13 nên số đã cho chia hết cho 13.
Ví dụ
#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";
}
} Đầu ra
Divisible