AtCoder Regular Contest 184 A,B問題メモ

n, m, q = map(int, input().split())
imitation = []
for i in range(50):
    s = i * 20 + 1
    zero = []
    one = []
    for j in range(s + 1, s + 20):
        print(f'? {s} {j}')
        res = input()
        if res == '0':
            zero.append(j)
        elif res == '1':
            one.append(j)
        else:
            exit()
    if len(zero) >= 10:
        # sとあわせて同種11枚
        imitation.extend(one)
    elif len(one) >= 11:
        imitation.append(s)
        imitation.extend(zero)
    else:
        # ちょうど10枚ずつ
        if i == 0:
            t = 21
        else:
            t = 1
        for j in range(s, s + 19):
            print(f'? {t} {j}')
            res = input()
            if res == '0':
                pass
            elif res == '1':
                imitation.append(j)
            else:
                exit()
        if len(imitation) < m:
            imitation.append(s + 19)

    if len(imitation) == m:
        break

    if i == 48 and len(imitation) == 0:
        s = 981
        t = 1
        for j in range(s, s + 19):
            print(f'? {t} {j}')
            res = input()
            if res == '0':
                pass
            elif res == '1':
                imitation.append(j)
            else:
                exit()
        if len(imitation) < m:
            imitation.append(s + 19)
        break

print('!', *imitation)

from bisect import bisect_right

import numpy as np
from numba import njit


@njit
def precompute():
    # ↓2倍, →3倍 という2次元表を考える
    #  1  3  9 27 81 ...
    #  2  6 18 54 ...
    #  4 12 36
    #  8 24 72

    # この表に出現する x <= 10^9 の各 x につき、
    # x 以下の全ての数を逆L字型（┌）のスタンプで塗るための最小個数を求めたい。
    # 出現する数の個数は300個程度と十分少ないため、事前計算して埋め込む。

    # x を決めたら、以下のDPで求められる。
    # DP[i,S] = i+1 行目以降の必要な数は全て塗られ、i 行目で塗られている列が集合 S である場合の最小回数
    # ※ i の大きい方から更新

    def loga(a, x):
        # 切り捨てる対数
        k = 1
        e = 0
        while k * a <= x:
            k *= a
            e += 1
        return e

    def pop_count_32(n):
        c = (n & 0x55555555) + ((n >> 1) & 0x55555555)
        c = (c & 0x33333333) + ((c >> 2) & 0x33333333)
        c = (c & 0x0f0f0f0f) + ((c >> 4) & 0x0f0f0f0f)
        c = (c & 0x00ff00ff) + ((c >> 8) & 0x00ff00ff)
        c = (c & 0x0000ffff) + ((c >> 16) & 0x0000ffff)
        return c

    n = 10 ** 9
    n_log2 = loga(2, n) + 1
    n_log3 = loga(3, n) + 1
    table = np.ones((n_log2, n_log3), np.int64)
    for j in range(1, n_log3):
        table[0, j] = table[0, j - 1] * 3
    for i in range(1, n_log2):
        table[i, :] = table[i - 1, :] * 2
        table[i, table[i, :] > n] = 0

    print(table)

    INF = 1 << 30
    result = {}
    for ti in range(n_log2):
        for tj in range(n_log3):
            x = table[ti, tj]
            if x == 0:
                break
            print(x)
            s = loga(2, x)
            limit = []
            for i in range(s, -1, -1):
                limit.append(loga(3, x >> i) + 1)
            dp = np.full(1 << limit[0], INF, np.int32)
            dp[0] = 0
            for i in range(s, 0, -1):
                lim0 = limit[s - i]
                lim1 = limit[s - i + 1]
                ndp = np.full(1 << lim1, INF, np.int32)
                mask0 = (1 << lim0) - 1
                mask1 = (1 << lim1) - 1
                for bitset in range(1 << lim0):
                    remain = bitset ^ mask0
                    sub_bitset = bitset
                    while True:
                        stamp = remain | sub_bitset
                        cnt = pop_count_32(stamp)
                        nxt = (stamp | (stamp << 1)) & mask1
                        ndp[nxt] = min(ndp[nxt], dp[bitset] + cnt)
                        if sub_bitset == 0:
                            break
                        sub_bitset = (sub_bitset - 1) & bitset

                dp = ndp

            result[x] = dp[-1]

    print(result)


# 事前計算
# precompute()

# 埋め込み（省略）
result23 = {
    1: 1, 3: 1, 9: 3, 27: 5, 81: 8, 243: 11, 729: 16, 2187: 20, 6561: 25, 19683: 31, 59049: 37, 177147: 44,
    # ...
}


def solve(n):
    if n <= 3:
        return 1
    if n <= 4:
        return 2
    if n <= 6:
        return 3

    xxx, counts = zip(*sorted(result23.items()))

    # 整数 k によって floor(N/k) と表せる整数の集合を求める
    lo = []
    hi = []
    for i in range(1, int(n ** 0.5) + 1):
        if i * i > n:
            break
        lo.append(i)
        h = n // i
        if h != i:
            hi.append(h)
    hi.reverse()
    lo.extend(hi)
    qqq = lo
    q_len = len(qqq)
    qqq_idx = {}
    for i in range(q_len):
        qqq_idx[qqq[i]] = i

    # qqq にある数 q に付き、「q以下のうち2と3の倍数でない数」の個数をLucyDPで求める
    dp0 = [q - 1 for q in qqq]
    for p in (2, 3):
        l = qqq_idx[p - 1]
        for j in range(q_len - 1, -1, -1):
            q = qqq[j]
            if p * p > q:
                break
            k = qqq_idx[q // p]
            dp0[j] -= dp0[k] - dp0[l]
    m = len(qqq)
    for i in range(2, m):
        dp0[i] -= 2
    dp0[1] -= 1
    ans = counts[bisect_right(xxx, n) - 1]
    for i in range(m - 1):
        c = dp0[i + 1] - dp0[i]
        ans += c * counts[bisect_right(xxx, n // qqq[i + 1]) - 1]
    return ans


n = int(input())

ans = solve(n)
print(ans)