Tóm tắt đề bài

Cho ~F(x) = ax + b~ và dãy số ~S = {S_1, S_2, ..., S_n}~ được xác định như sau:

• ~S_1 = c~
• ~S_i = F(S_{i-1}) \mod 100~ với ~2 \le i \le n~

Tìm số lớn thứ ~k~ trong dãy ~S~.

Giới hạn: (~a, b \le 10^9, c < 100, n \le 10^7~)

Subtask 1: ~n \le 2 \times 10^5~

Ở subtask này, ta hoàn toàn có thể mô phỏng dãy ~S~ từ ~S_1~ đến ~S_n~ do giới hạn ~n~ không quá to. Sau đó, ta sẽ sắp xếp dãy ~S~ để từ đó tìm được số lớn thứ ~k~.

Độ phức tạp: ~O~ (~n log n~)

Subtask 2: ~n \le 10^7~

Ta có thể để ý rằng, do giá trị ~mod~ tương đối nhỏ (tối đa ~100~), cũng đồng nghĩa giá trị của ~S~ không vượt quá ~99~. Từ đó, ta nhận ra rằng, hoàn toàn có thể sử dụng mảng đánh dấu để có thể đánh dấu số lần xuất hiện của từng phần tử ~S_i~ trong mảng ~S~.

Gọi ~cnt_i~ là số lần giá trị ~i~ xuất hiện trong mảng ~S~. Ta sẽ tiến hành duyệt từ cuối mảng ~cnt~ về đầu, và cộng số lần xuất hiện của giá trị ~i~ vào biến ~res~. Đáp số đề bài chính là giá trị ~i~ đầu tiên mà ~res \ge k~.

Độ phức tạp: ~O~ (~n~)