| Nộp bài | Các bài nộp | Làm tốt nhất | Về danh sách bài |
DIRICADD - Định lý Dirichlet về cấp số cộng |
Trong lý thuyết số, định lý Dirichlet về cấp số cộng được phát biểu một cách sơ cấp như sau:
Cho a, b là hai số nguyên dương nguyên tố cùng nhau, thế thì sẽ có vô hạn số nguyên tố có dạng a*n + b với n > 0.
Chẳng hạn với a = 4, n = 3, ta có cấp số cộng:
3, 7, 11, 15, 19, 23, 27, 31, 35, ...
Trong đó, các số nguyên tố là 3, 7, 11, 19, 23, 31, ...
Bài toán đặt ra: Cho trước a > 0, b ≥ 0, (a, b bất kì) và U ≥ L ≥ 0, nhiệm vụ của bạn là đếm xem có bao nhiêu giá trị t(n) = a*n + b là một số nguyên tố, với L ≤ n ≤ U
Trong lý thuyết số, định lý Dirichlet về cấp số cộng được phát biểu một cách sơ cấp như sau:
Cho a, b là hai số nguyên dương nguyên tố cùng nhau, thế thì sẽ có vô hạn số nguyên tố có dạng a*n + b với n > 0.
Chẳng hạn với a = 4, n = 3, ta có cấp số cộng:
3, 7, 11, 15, 19, 23, 27, 31, 35, ...
Trong đó, các số nguyên tố là 3, 7, 11, 19, 23, 31, ...
Bài toán đặt ra: Cho trước a > 0, b ≥ 0, (a, b bất kì) và U ≥ L ≥ 0, nhiệm vụ của bạn là đếm xem có bao nhiêu giá trị t(n) = a*n + b là một số nguyên tố, với L ≤ n ≤ U.
Input
Gồm nhiều test.
Mỗi bộ test gồm 4 số: a,b L, U, trong đó a*U + b ≤ 10^12, U - L ≤ 10^6.
Output
Với mỗi test, in ra như sau:
Case xxx: yyy
Trong đó, xxx là test thứ xxx, yyy là đáp số của bài toán.
Example
Input:
4 3 0 8 1 0 2 100 2 7 0 1000 0
Output:
Case 1: 6 Case 2: 25 Case 3: 301
| Được gửi lên bởi: | adm |
| Ngày: | 2013-01-25 |
| Thời gian chạy: | 5s |
| Giới hạn mã nguồn: | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Ngôn ngữ cho phép: | ASM32-GCC ASM32 MAWK BC C CSHARP C++ 4.3.2 CPP CPP14 COFFEE LISP sbcl DART FORTH GO JAVA JS-RHINO JS-MONKEY KTLN OCT PAS-GPC PAS-FPC PERL PERL6 PROLOG PYTHON PYTHON3 PY_NBC R RACKET SQLITE SWIFT UNLAMBDA |
