Cấp số nhân
Xem PDF
Điểm:
1600 (p)
Thời gian:
1.0s
Bộ nhớ:
1023M
Input:
bàn phím
Output:
màn hình
Cấp số nhân là một dãy số thỏa mãn điều kiện tỷ số giữa \(2\) phần tử liên tiếp là hằng số. Xét dãy cấp số nhân \(1,x,x^2,x^3,….,x^n\).
Yêu cầu: Cho 2 số nguyên \(x\) và \(n\). Tính tổng tất cả các phần tử trong cấp số nhân đã cho. Vì kết quả có thể rất lớn nên chỉ đưa ra số dư trong phép chia cho \(m\).
Input
- Một dòng chứa 3 số nguyên dương \(x,n,m \ (x \leq 100, n \leq 10^{18}, m \leq 10^7)\).
Output
- Một số nguyên là kết quả của bài toán.
Example
Test 1
Input
2 6 1000 Output
127Note
Giải thích: \(.2^0+2^1+2^2+2^3+2^4+2^5+2^6=1+2+4+8+16+32+64=127\).
Bình luận
Mình xin trình bài lời giải bài này theo 2 cách như sau:
Cách 1: Chia để trị :
Đặt \(G(p,n)=1+p+...+p^{n}\rightarrow (1)\).
Công việc tiếp theo của chúng ta là đi tính \(G(p,n)\), và chúng được thực hiện như sau:
Ta có: \(G(p,n)=\left\{\begin{matrix} 1, \text{ với }n=0 \\ 1+p, \text{ với } n=1 \\ 1 + p*G(p,n-1), \text{ với } n \text{ lẻ } \\(1+p^{\frac{n}{2}})[G(p,\frac{n}{2})-1]+1=(1+p^{\frac{n}{2}})(1+p+...+p^{\frac{n}{2}}-1)+1, \text{ với } n \text{ chẵn }\end{matrix}\right.\)
Và độ phức tạp để tính \(G(p,n)\) là \(O(log(n))\)
Và các bạn có thể tham khảo code tại đây: Link
Cách 2: nhân ma trận.
Từ \((1)\implies G(p,n+1) = G(p,n)*p+1\)
Đặt \(F[n]=G(p,n)\). Khi đó ta có: \(F[n+1]=p*F[n]+1\)
\(\implies \begin{pmatrix}F[n] & 1\end{pmatrix}.\begin{pmatrix}p & 0 \\ 1 & 1\end{pmatrix} = \begin{pmatrix}F[n+1] & 1\end{pmatrix}\)
Đến đây, đặt \(p_n=\begin{pmatrix}F[n] & 1\end{pmatrix}\). và \(M=\begin{pmatrix}p & 0 \\ 1 & 1\end{pmatrix}\). Ta có: \(p_{n+1}=p_n.M=p_{n-1}.M^{2}=...=p_0.M^n\). Với \(p_0=\begin{pmatrix}1 & 1\end{pmatrix}\)
Đến đây sử dụng luỹ thừa nhị phân trên ma trận là ta đã giải quyết xong bài toán.
Các bạn có thể tham khảo code tại đây:Link
5 bình luận nữa