Editorial for Bedao Grand Contest 11 - FRACTION


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: bedao

Ta có số "k-phân" được viết dưới định dạng:

~d.eb~

Với:

  • ~d~ là phần nguyên.
  • ~e~ là phần "k-phân" không vô hạn tuần hoàn.
  • ~b~ là phần "k-phân" vô hạn tuần hoàn.

Ta sẽ biến đổi từng phần từ dạng "k-phân" về dạng phân số thập phân rồi cộng các phân số lại để được kết quả cuối cùng, cách biến đổi từng phần như sau:

Biến đổi ~d~ từ số "k-phân" về dạng phân số thập phân

Xem ~d~ là dãy số gồm ~D~ chữ số: ~d_1d_2d_3\dots d_D~, công thức chuyển đổi về dạng thập phân là:

~d = \sum_{i=1}^D d_ik^{D-i}~

Biến đổi ~0.e~ từ số "k-phân" về dạng phân số thập phân

Xem ~e~ là dãy số gồm ~E~ chữ số: ~e_1e_2e_3\dots e_E~, công thức chuyển đổi ~0.e~ về dạng thập phân là:

~0.e =\frac{e}{k^E}=\frac{1}{k^E}\sum_{i=1}^E e_ik^{E-i}~

Biến đổi ~0.b~ về dạng phân số thập phân

Lưu ý, ~b~ là một dãy số có vô hạn chữ số tuần hoàn. Ta gọi ~B~ là độ dài của một dãy số tiền tố bất kỳ sao cho:

~b_i=b_{i \texttt{ mod } B}~

Ta gọi:

~T = \sum_{i=1}^B b_ik^{B-i} ~

Ta có công thức chuyển đổi từ ~0.b~ thành dạng phân số thập phân như sau:

~0.b \times k^B = T.b~

~\Rightarrow T.b - 0.b=0.b\times (k^B-1)~

~\Rightarrow T=0.b\times (k^B-1)~

~\Rightarrow 0.b = \frac{T}{k^B-1} = \frac{1}{k^B-1}\sum_{i=1}^B b_ik^{B-i}~

Cách cộng các phần lại thành kết quả cuối cùng

Ta có số "k-phân" được viết dưới định dạng:

~d.eb~

Từ định dạng trên ta có thể viết lại thành tổng như sau:

~d.eb=d+0.e+\frac{0.b}{k^E}~

~=\sum_{i=1}^D d_ik^{D-i} + \frac{1}{k^E}\sum_{i=1}^E e_ik^{E-i} + \frac{1}{k^E(k^B-1)}\sum_{i=1}^B b_ik^{B-i}~


Comments

Please read the guidelines before commenting.


There are no comments at the moment.