Good Numbers (hard version) (Codeforces 1249C2)
Tags: Greedy, meet-in-the-middle

The only difference between easy and hard versions is the maximum value of $$$n$$$.You are given a positive integer number $$$n$$$. You really love good numbers so you want to find the smallest good number greater than or equal to $$$n$$$.The positive integer is called good if it can be represented as a sum of distinct powers of $$$3$$$ (i.e. no duplicates of powers of $$$3$$$ are allowed).For example:  $$$30$$$ is a good number: $$$30 = 3^3 + 3^1$$$,  $$$1$$$ is a good number: $$$1 = 3^0$$$,  $$$12$$$ is a good number: $$$12 = 3^2 + 3^1$$$,  but $$$2$$$ is not a good number: you can't represent it as a sum of distinct powers of $$$3$$$ ($$$2 = 3^0 + 3^0$$$),  $$$19$$$ is not a good number: you can't represent it as a sum of distinct powers of $$$3$$$ (for example, the representations $$$19 = 3^2 + 3^2 + 3^0 = 3^2 + 3^1 + 3^1 + 3^1 + 3^0$$$ are invalid),  $$$20$$$ is also not a good number: you can't represent it as a sum of distinct powers of $$$3$$$ (for example, the representation $$$20 = 3^2 + 3^2 + 3^0 + 3^0$$$ is invalid). Note, that there exist other representations of $$$19$$$ and $$$20$$$ as sums of powers of $$$3$$$ but none of them consists of distinct powers of $$$3$$$.For the given positive integer $$$n$$$ find such smallest $$$m$$$ ($$$n \le m$$$) that $$$m$$$ is a good number.You have to answer $$$q$$$ independent queries.

Input: The first line of the input contains one integer $$$q$$$ ($$$1 \le q \le 500$$$) — the number of queries. Then $$$q$$$ queries follow.The only line of the query contains one integer $$$n$$$ ($$$1 \le n \le 10^{18}$$$).

Output: For each query, print such smallest integer $$$m$$$ (where $$$n \le m$$$) that $$$m$$$ is a good number.


Sample Inputs:
8
1
2
6
13
14
3620
10000
1000000000000000000

Sample Outputs:
1
3
9
13
27
6561
19683
1350851717672992089

Solution (Python):
a = [3 ** i for i in range(40)]
q = int(input())
for _ in range(q):
    n = int(input())
    res = sum(a)
    for t in a[::-1]:
        if res - t >= n:
            res -= t
    print(res)

Solution (Python):
t = int(input())
for i in range(t):
    rr = []
    n = int(input())
    r = 0
    k = 1
    while n > 0:
        if n % 3 == 2:
            r = 0
            n //= 3
            n += 1
        else:
            r += k * (n % 3)
            n //= 3
        k *= 3
    rr.append(r)
    print(*rr)

Solution (Python):
arr = [3 ** i for i in range(40)]
s = sum(arr)
t = int(input())
for _ in range(t):
    n = int(input())
    m = s
    for i in arr[::-1]:
        if m - i >= n:
            m -= i
    print(m)