Subtask 1

Vì chỉ có 38 giá trị $3^x\le {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 lo{g}_{10}{3}^x\rfloor \le lo{g}_{10}{3}^x=x\cdot lo{g}_{10}3$.

Vì số chữ số của $N$ không vượt quá $1000$ nên $x\cdot lo{g}_{10}3\le 1000\Rightarrow x\le 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\ge 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\le 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\ast lo{g}^{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\mathrm{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\mathrm{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 logM)$ hoặc $O(M)$ với $M$ là tổng số chữ số của $N$.