Hint 1: Ta chỉ có \(f_1, f_2, ..., f_{90}\). Vậy các số Fibonacci có quan trọng không?

Hint 2: Có thể tính \(u(n)\) nhanh không?

Hint 3: Có thể tính \(g(n)\) nhanh không?

Lời giải:

Đầu tiên ta có thể tính hết mọi số \(f_0, f_1, ..., f_{90}\) vì các số này đều chứa được trong long long. Nếu chúng ta tính được \(g(n)\) với \(n\) bất kỳ thì phần còn lại là đơn giản. Vì vậy, chúng ta sẽ tập trung tính \(g(n)\) như sau:

Thấy rằng, \(u(1) = 1, u(2) = 2, ..., u(9) = 9, u(10) = 19, u(11) = 29, ..., u(18) = 99, u(19) = 199, ...\). Như vậy, \(u(n)\) có quy luật với chu kỳ là 9 và luôn có dạng \(x9999..999\) với \(x\) được tính theo \(n % 9\). Để tính toán đơn giản, có thể viết lại \(x99..99 = (x + 1) * 10^y - 1\) với \(y\) cũng được tính theo \(n / 9\). Như vậy, \(g(n)\) có thể được tính bằng cách tổng các lũy thừa của 10.

Ví dụ, \(g(20) + 20 = 2 * 10^0 + 3 * 10^0 + ... + 10 * 10^0 + 2 * 10^1 + 3 * 10^1 + ... + 10 * 10^1 + 2 * 10^2 + 3 * 10^2\).