Gợi ý #0

Sử dụng truy vấn \(MO\).

Gợi ý #1

Bổ đề: \(a_na_{n - 1}a_1...a_na_{n - 1}a_1\:\text{(k lần)} = \frac{10^{kn} - 1}{10^n - 1} \times a_na_{n - 1}a_1\). Ví dụ \(12121212 = \frac{(10^{4\times 2} - 1)}{99} \times 12\).

\(\to\) Đưa về bài toán tìm cấp (multiplicative order) của \(10\) theo một modulo \(M\).

Gợi ý #2

Trong các bổ đề sau \(a, m, n\) là các số nguyên dương và \(x, y\) là các số nguyên.

Định lý Fermat nhỏ: Nếu \(p\) là số nguyên tố và \(gcd(a, p) = 1\) thì \(a^{p - 1} = 1\:[p]\).

Bổ đề \(1\): \(i\) là số nguyên dương nhỏ nhất sao cho \(a^i = 1\:[m]\) và \(j\) là số nguyên dương bất kì sao cho \(a^j = 1\:[m]\) thì \(i|j\).

Bổ đề \(2\): \(i\) là số nguyên dương nhỏ nhất sao cho \(a^i = 1\:[m]\), \(j\) là số nguyên dương nhỏ nhất sao cho \(a^j = 1\:[n]\) và \(gcd(m, n) = 1\) thì \(x = lcm(i, j)\) là số nguyên dương nhỏ nhất sao cho \(a^x = 1\:[mn]\).

Bổ đề \(3\): Nếu \(i\) là số nguyên dương nhỏ nhất sao cho \(a^i = 1\:[m]\) thì \(x = \frac{i}{gcd(i, k)}\) là số nguyên dương nhỏ nhất sao cho \(a^{kx} = 1\:[m]\)

Bổ đề \(4\) (Bổ đề LTE): Với \(p\) là số nguyên tố lẻ và \(p|x - y\) thì: \(v_p(x^n - y^n) = v_p(x - y) + v_p(n)\), với \(v_p(n)\) là mũ của tsnt \(p\) trong \(n\).

Gợi ý #3

Tạo CTDL để tính nhanh BCNN trong một đoạn số trên dãy số:

• Thêm phần tử \(n\).
• Xóa phần tử \(n\).
• Nhân cho \(k\).
• Chia cho \(k\).
• Tìm BCNN của đoạn số.
• Tìm ƯCLN của đoạn số với một số.

Gợi ý #4

Sử dụng sàng Euler để phân tích nhanh thành tích các thừa số nguyên tố.

Tính trước các giá trị \(x\) nhỏ nhất mà \(10^x = 1\:[p^k]\) với mỗi số nguyên tố \(p\) và số nguyên dương \(k\) mà \(p^k < 1000000\).

Duyệt trên tích các tsnt để tìm nhanh số mũ nhỏ nhất trong \(O(log)\).

Chú ý rằng với \(p = 2\) và \(p = 5\) thì phương trình \(10^x = 1\:[p]\) vô nghiệm.

Gợi ý #5

Sử dụng cây phân đoạn rời rạc cho CTDL tìm BCNN: unordered_map<int, SegmentTree> pows với pows[p] là dãy các số mũ \(k\) của tsnt \(p\) của các số trong đoạn.

Độ phức tạp cuối cùng là \(O(QlogQ + (N + Q)\sqrt{N}log(log(N))log(1000000))\).