| Nộp bài | Các bài nộp | Làm tốt nhất | Về danh sách bài |
P156SUMJ - ROUND 6J - Dãy số Fibonacci và phép toán UCLN |
Tí được cô giáo ưu ái một bài tập đặc biệt về dãy Fibonacci như sau: Hãy tìm UCLN của 2 số A, B được xác định bởi công thức: A = a[0]F[n]+a[1]F[n+1]+a[2]F[n+2] và B = b[0]F[n]+b[1]F[n+1]+b[2]F[n+2].
Trong đó là số Fibonacci thứ n. Dãy số Fibonacci được xác định bằng công thức truy hồi:
F[0] = 0, F[1] = 1; F[n] = F[n-1] + F[n-2].
Tí loay hoay một hồi chưa nghĩ ra cách giải quyết. Các bạn hãy giúp Tí nhé!
Input
Dòng đầu tiên là gồm số lượng bộ test T (T <= 100 000).
T dòng tiếp theo, mỗi dòng gồm 8 số nguyên n, a0, a1, a2, b0, b1, b2, M. Vì đáp số có thể rất lớn nên kết quả được lấy mod theo modulo M.
Giới hạn: n <= 10^15, 0 <= a[i], b[i] <= 1000, M <= 10^9.
Output
Với mỗi test, in ra số đáp án của bài toán.
Example
Input:2
5 2 3 4 6 7 10 100
5 2 3 4 0 0 0 100
Output:2
86
Giải thích test 1: Số fibo thứ 5, 6, 7 lần lượt là 5, 8, 13. Ta có A = 86, B = 216, ULCN(A, B) = 2.
| Được gửi lên bởi: | adm |
| Ngày: | 2015-08-06 |
| Thời gian chạy: | 4s |
| 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 KTLN OCT PAS-GPC PAS-FPC PERL PERL6 PROLOG PYTHON PYTHON3 PY_NBC R RACKET SQLITE SWIFT UNLAMBDA |
hide comments
|
2020-02-03 16:29:23
Lần trước submit thì đúng rồi bây giờ bị reject, bài này thay test hay sao mà resubmit không AC. |
|
|
2016-06-13 14:41:55
MÌnh xin góp ý kiến: - Mỗi bài post nên nói rõ đầu vào và đầu ra.(cái này quan trọng) - Và mình không hiểu trình test online sẽ test = cách nào. Mình chạy = code block thì ổn rồi, ra đúng kết quả. mà post nên thì báo làm sai. |
|
|
2015-08-14 08:52:15 TICHPX
trong trường hợp a0=a1=a2=b0=b1=b2=0 thì out là gì nhỉ |
