ต่อไปเราจะมาดูวิธีการเช็คจำนวนหารด้วย 13 กัน ว่าลงตัวหรือไม่ ในกรณีนี้จำนวนเป็นจำนวนที่มาก ดังนั้นเราจึงใส่ตัวเลขเป็นสตริง
ตัวเลขจะถูกหารด้วย 13 หากตัวเลขตรงกับสถานการณ์ต่อไปนี้ -
- ตัวเลขหารด้วย 13 ลงตัวก็ต่อเมื่อเราได้ผลรวมสลับกัน เช่น บวกและลบบล็อกของตัวเลขสามตัวจากขวาไปซ้ายหารด้วย 13 ลงตัว เช่น 2911285 หารด้วย 13 ลงตัวเพราะว่าผลรวมสลับกันของ บล็อคขนาด 3 คือ 2 – 911 + 285 =-650 ซึ่งหารด้วย 13 ลงตัว
- ตัวเลขหารด้วย 13 ลงตัวก็ต่อเมื่อตัวเลขนั้นเกิดจากการบวกเลขหลักสุดท้ายคูณ 4 เข้ากับส่วนที่เหลือหารด้วย 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
