Subtask 1

Vì chỉ có 38 giá trị ~3^x \leq 10^{18}~, nên với mỗi ~N~ ta chỉ cần duyệt ~38~ giá trị đó rồi kiểm tra xem có bằng ~N~ hay không.

ĐPT: ~O(T)~

Sutask 2

Số chữ số của ~3^x~ có thể được được tính bằng hàm ~\lfloor log_{10}{3^x} \rfloor \leq log_{10}{3^x} = x \cdot log_{10}{3}~.

Vì số chữ số của ~N~ không vượt quá ~1000~ nên ~x \cdot log_{10}{3} \leq 1000 \Rightarrow x \leq 2095~.

Cho nên, ta chỉ cần duyệt ~2095~ giá trị ~3^x~ đầu tiên với mỗi ~N~ rồi kiểm tra xem có bằng ~N~ hay không. Vì ~3^x~ lớn nên ta không thễ biểu diễn dưới dạng long long được. Thay vào đó, ta xử lý số lớn bằng kiểu dữ liệu string hoặc vector. Lưu ý break sớm nếu giá trị ~3^x \geq N~, nếu không sẽ bị TLE.

ĐPT: ~O(M^2)~ với ~M~ là tổng số chữ số của ~N~.

Subtask 3

Sử dụng ý tưởng của subtask 2, ta rút được ~x \leq 2095903~.

Dễ dàng thấy được giới hạn này sẽ không cho ta sử dụng bignum được.

Or can it?

Bài toán có thể giải quyết trong ~O((M * log^2{M})/ 32)~ bằng nhân lũy thừa nhị phân bignum kết hợp vớt fft và chuyển về hệ cơ số 1e9.

Thay vào đó, ta dùng kỹ thuật hashing. Với mỗi ~3^x~, ta tính giá trị ~3^x \mod MOD~, với ~MOD~ là một số nguyên tố lớn bất kì. Như vậy, với mỗi ~N~, ta chỉ cần tìm giá trị ~N \mod MOD~, sau đó kiểm tra qua giá trị hash đó. Nếu ta để ~MOD~ đủ lớn và nằm trong kiểu dữ liệu long long, thì ta có thể tiền xử lý các giá trị hash của ~3^x~ rồi đưa vào ctdl map để kiểm tra nhanh và đảm bảo rủi ro bị trùng hash (Lưu ý không được dùng unordered_map!!!).

Việc dùng unordered_map tuy chạy nhanh trong một số trường hợp nhưng trường hợp xấu nhất vẫn luôn là ~O(N^2)~, trên một số trang thi như codeforces thì bạn có thể bị hack bởi người khác nếu bị lộ code.

Việc tính các giá trị hash của ~3^x~ hay ~N~ khá dễ nên mình xin nhường cho bạn đọc (i'm lazy).

ĐPT: ~O(M \cdot log{M})~ hoặc ~O(M)~ với ~M~ là tổng số chữ số của ~N~.