Cho hai số a, b. Kiểm tra a có chia hết cho tất cả ước nguyên tố của b không.
Ví dụ: a=120 (ước NT: 2,3,5), b=75 (ước NT: 3,5). 120 chia hết 3 và 5 → YES.
Giải thuật
- Nếu b=1 → true (không có ước nguyên tố)
- Tính gcd = GCD(a, b)
- Nếu gcd=1 → false (nguyên tố cùng nhau)
- Đệ quy: kiểm tra a với b/gcd
Ý tưởng: gcd chứa tất cả ước NT chung. b/gcd chứa ước NT riêng của b. Nếu a chia hết cho b/gcd → OK.
Ví dụ minh họa
#include <iostream>
#include <algorithm>
using namespace std;
bool isDivisible(int a, int b) {
if (b == 1) return true;
int gcd = __gcd(a, b);
if (gcd == 1) return false;
return isDivisible(a, b / gcd);
}
int main() {
int a = 120, b = 75;
if (isDivisible(a, b))
cout << a << " chia het cho tat ca uoc nguyen to cua " << b;
else
cout << a << " KHONG chia het cho tat ca uoc nguyen to cua " << b;
}
Kết quả
120 chia het cho tat ca uoc nguyen to cua 75