Link Sub: http://www.spoj.com/PTIT/problems/PTIT017J/
Người Gửi: Dương Lee
- Problem:
Cho 5 số tự nhiên a, b, c, d, e là các số nguyên tố cùng nhau từng đôi một. Hãy cho biết có bao nhiêu số nhỏ hơn hoặc bằng N không chia hết cho bất kỳ số nào trong các số a, b, c, d, e (N<263) Input
Dòng đầu tiên là số lượng bộ test T (T ≤ 50).
Mỗi test gồm hai dòng: dòng đầu tiên ghi lại số N, dòng kế tiếp ghi lại 5 số a, b, c, d, e nguyên tố cùng nhau (cả 5 số đều không quá 1000).
Output
Ứng với mỗi test đưa ra số lượng các số không chia hết cho bất kể số nào trong các số a, b, c, d, e
Example:
Ứng với mỗi test đưa ra số lượng các số không chia hết cho bất kể số nào trong các số a, b, c, d, e
Input
3
1000
2 3 5 7 11
10000
3 4 5 7 11
1000000000
9 11 13 17 19
Output:
207
3116
665093420
- Solution:
- Bài này dựa vào toán rời rạc 1 để làm
VD:
Số lượng các số chia hết cho 2 (<= N) là: [N/2] (trong đó [] là chia lấy nguyên).
Số lượng các số chia hết cho 3 (<= N) là: [N/3] (trong đó [] là chia lấy nguyên).
Số lượng các số chia hết cho cả 2 và 3 (<= N) là: [N/6] (trong đó [] là chia lấy nguyên).
-> Số lượng các số không chia chia hết cho 2 và 3 (<= N) là: N - ([N/2] + [N/3] - [N/6]) (trong đó [] là chia lấy nguyên).
Tổng quát:
Với 5 số A, B, C, D, E thì:
ta có đáp án: = N - ([N/A]+[N/B]+..+[N/E] -[N/(A*B)]-[N/(A*C)]-...-N[N/(D*E)] +[N/(A*B*C)]+[N/(A*B*D)]+...+[N/(C*D*E)]) -[N/(A*B*C*D)]-...-[N/(B*C*D*E)] +[N/(A*B*C*D*E)])
Ví dụ cho 3 số A=2 B=3 C=5, biểu diễn các số chia hết cho A, B, C theo dạng tập hợp;
trong đó S (x) là tập các số chia hết cho x.
Việc cần làm giờ là chỉ cần sinh nhị phân chọn các cặp số và tính toán số lượng các số của các cặp tích số.