| Nộp bài | Các bài nộp | Làm tốt nhất | Về danh sách bài |
P162SUME - Round 2E - Rút gọn phân số |
Lúi rất thích tìm hiểu về phân số, đặc biệt là về bài toán rút gọn phân số.
Lúi có một số nguyên tố x và n số nguyên không âm a1, a2, …, an. Với các số nguyên này, Lúi muốn thực hiện phép tình sau: 
. Điều đặc biệt là phân số kết quả phải có mẫu số là x ^ (a1 + a2 + … + an).
Sau một hồi hỳ hục tính toán thì cuối cùng Lúi cũng tình được phân số cuối cùng. Và giờ là đến phần Lúi thích nhất - rút gọn phân số. Để rút gọn 1 phân số thì tất nhiên ta phải đi tìm ước chung lớn nhất của tử số và mẫu số. Vì kết quả là 1 số có tử số và mẫu số đều là các số lớn nhất nên việc tìm ước chung lớn nhất có vẻ đang rất thức tạp :/. Bạn có thể giúp Lúi giải quyết vấn đề này không.
Input
Dòng đầu là số nguyên n, x (1 <= n <= 10^5, 2 <= x <= 10^9)
Dòng tiếp theo là n số nguyên a1, a2, a3, …, an (0 <= a1 <= a2 <= … <= an <= 10^9)
Output
In ra số nguyên duy nhất là ước chung lớn nhất của tử số và mẫu số phân số tổng. Vì kết quả có thể là 1 số rất lớn nên ta sẽ mấy modulo 1000000007 (1e9 + 7).
Example
Input: 3 3
1 2 3
Output:
27
Input: 6 3
0 0 0 0 0 0
Output:
1
Input: 3 2
4 5 5
Output:
2048
Giải thích:
Test 1: 1/3 + 1/9 + 1/27 = (243 + 81 + 27) / 729 = 351 / 729 -> GCD(351, 729) = 27
Test 2: 1/1 + 1/1 + 1/1 + 1/1 + 1/1 + 1/1= 6/1 -> GCD(6, 1) = 1
Test 3: 1/16 + 1/32 + 1/32 = (1024 + 512 + 512)/16384 = 2048/16384
-> GCD(2048, 16384) = 2048
| Được gửi lên bởi: | adm |
| Ngày: | 2016-07-14 |
| Thời gian chạy: | 1s-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 KTLN OCT PAS-GPC PAS-FPC PERL PERL6 PROLOG PYTHON PYTHON3 PY_NBC R RACKET SQLITE SWIFT UNLAMBDA |
