K nguyên tố
Xem dưới dạng PDFMột đoạn \([L;R]\) được gọi là KPRIME nếu có ít nhất \(K\) số nguyên tố thuộc đoạn đó.
Cho \(2\) số nguyên dương \(N\) và \(K\).
Hỏi có bao nhiêu đoạn con của đoạn \([1;N]\) là đoạn KPRIME?
Chú thích: Đoạn con của \([1;N]\) là một đoạn \([L;R]\) sao cho \(L , R\) là các số nguyên và \(1 \le L \le R \le N\)
Input
- Gồm 2 số nguyên dương \(N\) và \(K\)
Output
- Một số nguyên duy nhất là số lượng đoạn \([L;R]\) là đoạn con của đoạn \([1;N]\) có ít nhất \(K\) số nguyên tố thuộc nó.
Ràng buộc:
- Có 50% số lượng test khác thỏa mãn điều kiện: \(n \le 10^3 , k \le 10^3\);
- Có 25% số lượng test khác thỏa mãn điều kiện: \(n \le 10^5 , k \le 10^4\);
- Có 25% số lượng test khác thỏa mãn điều kiện: \(n \le 10^7 , k \le 10^5\);
Sample input
8 2Sample out
20Giải thích ví dụ:
Có \(20\) đoạn \([L;R]\) thõa mãn điều kiện là đoạn con của \([1;8]\) và có ít nhất \(2\) số nguyên thuộc nó.
\([1;3], [1;4], [1;5], [1;6], [1;7], [1;8]\),
\([2;3], [2;4], [2;5], [2;6], [2;7], [2;8]\),
\([3;5], [3;6], [3;7], [3;8]\),
\([4;7], [4;8]\),
\([5;7], [5;8]\).
Nhận xét
AC rồi!!! Tui sẽ dùng cái này bùa hộ mệnh 9+ Ngữ văn:)))))))))))))))))))))
hehehehehehehee