| Nộp bài | Các bài nộp | Làm tốt nhất | Về danh sách bài |
PTIT133A - Tìm phần tử nhỏ nhất |
Tèo đang chơi trò chơi với dãy số. Tèo có tập hợp m, gồm n phần tử không âm. (Phần tử đầu tiên là m[0]). Tèo đã biết trước k số đầu tiên, được xác định theo công thức:
m[0] = a
m[i] = (b * m[i - 1] + c) % r, 0 < i < k
Với mỗi i (k <= i < n), m[i] là số nguyên không âm nhỏ nhất không có mặt trong k phần tử cuối của tập m hiện tại. Các phần tử còn lại xây dựng theo quy tắc này.
Ví dụ, với k = 3, n = 4, tập m ban đầu gồm 3 phần tử {2, 3, 0}, thì phần tử thứ 4 của tập hợp sẽ là m[3] = 1.
Nhiệm vụ của bạn là giúp Tèo xác định phần tử thứ n (m[n-1]) là bao nhiêu?
Input
Dòng đầu tiên là số test (<=20).
Mỗi test gồm 2 dòng:
Dòng 1: 2 số n, k ( 1 <= k <= 105, k < n <= 109).
Dòng 2 gồm 4 số a, b, c, r (0 <= a, b, c <= 109, 1 <= r <= 109).
Output
Với mỗi trường hợp, in ra phần tử thứ n của tập hợp theo mẫu dưới đây.
Example
Input:
5 97 39 34 37 656 97 186 75 68 16 539 186 137 49 48 17 461 137 98 59 6 30 524 98 46 18 7 11 9 46Output:
Case #1: 8 Case #2: 38 Case #3: 41 Case #4: 40 Case #5: 12
| Được gửi lên bởi: | adm |
| Ngày: | 2013-02-08 |
| Thời gian chạy: | 2s |
| 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 |
hide comments
