Số dư
Xem PDF
Điểm:
1700 (p)
Thời gian:
1.0s
Bộ nhớ:
256M
Input:
bàn phím
Output:
màn hình
Giờ học về phép chia có dư tỏ ra quá dễ dàng cho các bé trường mầm non SuperKids, để tăng tính hấp dẫn cho giờ học, cô giáo muốn đặt ra một thách thức mới.
Cho ba số nguyên dương \(x, n, m\). Cô giáo xét dãy chữ số là biểu diễn thập phân của \(x\) và viết lặp đi lặp lại dãy chữ số này \(n\) lần để được biểu diễn thập phân của một số \(y\). Nhiệm vụ của các bé là phải cho biết số dư của \(y\) khi chia cho \(m\).
Ví dụ với \(x = 12, n = 3, m = 8\). Số \(y = 121212\), số dư của \(y\) khi chia cho 8 là 4.
Các bé làm việc rất hào hứng và nhanh chóng đưa ra kết quả, vấn dề của cô giáo là cần biết kết quả đúng để phát phiếu bé ngoan cho các bé làm đúng và nhanh nhất. Em hãy giúp cô giáo tính toán kết quả.
Input
- Một dòng chứa 3 số guyên dương \(x, n, m. (x, n, m \le 10^{18})\)
Output
- Một số nguyên dương là số dư của y khi chia cho \(m\).
Example
Test 1
Input
12 3 8Output
4
Bình luận
Mình xin chia sẻ lời giải bài này như sau:
Gọi \(len(x)\) là số chữ số của \(x\) và gọi \(F[n]\) là kết quả của bài toán cần tìm.
Khi đó ta có công thức truy hồi sau: \(F[n]=(F[n-1]*10^{len(x)}+x)\text{ % }m=F[n-1]*(10^{len(x)}\text{ % }m)+(x\text{ % }m)\)
Đặt \(p=10^{len(x)}\text{ % }m\) và \(q=x\text{ % }m\)
Khi đó ta có: \(F[n]=p*F[n-1]+q\rightarrow (1)\), trong đó: \(F[1]=q\) và \(p,q\) dễ dàng ta tính được. (Chú ý: Để tính \(p\) ta sử dụng luỹ thừa nhị phân).
Đến đây ta có hai hướng tiếp cận để giải quyết bài toán này:
Cách 1: Dùng nhân ma trận (một thuật toán hữu hiệu trong trường hợp này), và cách giải như sau:
Từ \((1)\implies \begin{pmatrix}F[n-1] & 1 \end{pmatrix}.\begin{pmatrix}p & 0 \\ q & 1\end{pmatrix}=\begin{pmatrix}F[n] & 1 \end{pmatrix}\)
Đặt \(p_n=\begin{pmatrix}F[n] & 1 \end{pmatrix}\) và \(M=\begin{pmatrix}p & 0 \\ q & 1\end{pmatrix}\)
Ta suy ra được: \(p_{n}=p_{n-1}*M=p_{n-2}.M^2=...=p_{1}*M^{n-1}\) trong đó: \(p_1=\begin{pmatrix}q & 1\end{pmatrix}\)
Và đến đây, ta sử dụng tiếp tục sử dụng luỹ thừa nhị phân và phép nhân ma trận để giải quyết bài toán.
Nhưng một điều cần lưu ý trong thực hiện phép nhân ma trận cũng như luỹ thừa nhị phân khi làm đó là để thực hiện phép nhân \(X\text{ x }Y\text{ mod } MOD\), ta cũng nên sử dụng luỹ thừa nhị phân để tránh bị tràn số dẫn đến bị sai kết quả cuối cùng.
Và đây là code của mình cho cách 1: Link
Cách 2: Sử dụng phép biến đổi thông thường, và chúng được thực hiện như sau:
Từ \((1)\implies F[n]=p*F[n-1]+q=p*(p*F[n-2]+q)+q=p^2*F[n-2]+q(1+q)=...\)
\(=p^{n-1}*F[1]+q*(1+p+...+p^{n-2})\)
Hay \(F[n]=p^{n-1}*F[1]+q*(1+p+...+p^{n-2})\)
Đặt \(G(p,n)=1+p+...+p^{n}\). Khi đó \(F[n] = p^{n-1}*q + q*G(p,n-2)\).
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))\)
Như vậy, bài toán đã được giải quyết xong.
Các bạn có thể tham khảo code cách 2 tại đây: Link
Ps: Nếu có gì thắc mắc các bạn cứ comment nhé.