Nhận xét 1: Số cô đơn là số không chia hết cho các số từ ~2~ tới ~10~.

Gọi ~s[k]~ là số cô đơn thứ ~k~.

Subtask 1:

• Với mỗi testcase, ta duyệt O(v) cho câu hỏi đầu, và O(s[k]) cho câu hỏi thứ hai.

• Như vậy tổng cộng ĐPT là ~O(T * max(v, s[k]))~ ~\approx~ ~10^7~.

Subtask 2:

• Tiền xử lí trước các câu trả lời.

• Do đó ĐPT cho tiền xử lý ~O(10^6)~, và xử lý trong ~O(1)~.

Nhận xét 2: Không cần phải quan tâm cả ~9~ giá trị, ta chỉ cần quan tâm tới ~2~, ~3~, ~5~, và ~7~.

Subtask 3, 4:

• Để xác định số ~v~ là số cô đơn thứ bao nhiêu, ta sử dụng bao hàm loại trừ. Cụ thể, ta sẽ xác định cố bao nhiêu số không cô đơn mà bé hơn ~v~. Lượng số không cô đơn đó có thể xác định như sau:

  • ~+~ [~v / 2~ + ~v / 3~, ~v / 5~, ~v / 7~] số.

  • ~-~ [~v / (2 * 3)~ + ~v / (2 * 5)~ + ~\ldots~ + ~v / (5 * 7)~] số.

  • ~+~ [~v / (2 * 3 * 5)~ + ~v / (2 * 3 * 7)~ + ~v / (3 * 5 * 7)~] số.

  • ~-~ [~v / (2 * 3 * 5 * 7)]~ số.

• Như vậy, để tìm được vị trí của số cô đơn ~v~. Ta có thể tính qua công thức:

  • Vị trí của số cô đơn ~v~ ~=~ ~v~ ~-~ số lượng số không cô đơn mà bé hơn ~v~.

• Để xác định số cô đơn thứ ~k~, ta sẽ dùng chặt nhị phân để tìm.

• Ở subtask 3, nếu không thể đưa ra nhận xét giảm số lượng số xuống 4 số như nhận xét 2 đã nói ở trên, thì ta sẽ bị TLE nếu ~k~ quá lớn. Lúc này ta dùng tiền xử lí như Subtask 2 để tìm ~s[k]~.

• Như vậy ĐPT cho Subtask 3 sẽ là ~O(T * 2^9)~. Từ Nhận xét 2, ta có ĐPT cho Subtask 4 sẽ là ~O(T * log(s[10^{18}]) * 2^4)~.

#include <bits/stdc++.h>

#ifdef LOCAL
#include </home/cas/Cp/Lib/debug.h>
#else
#define console(...) void(10062006)
#endif

using namespace std;
using ll = long long;
using ull = unsigned long long;

int num[] = {2, 3, 5, 7};

ll calc(ll n) {
    ll ret = 0;

    for(int ms = 0; ms < (1 << 4); ++ms) {
        int mul = 1;
        for(int i = 0; i < 4; ++i) 
            if(ms >> i & 1) mul *= num[i];
        ret += 1LL * n / mul * (__builtin_popcount(ms) & 1 ? -1 : 1);
    }
    return ret;
}

int main() {
    int testcase; 
    cin >> testcase;

    while(testcase--) {
        ll v, k;
        cin >> v >> k;

        // solve first problem
        cout << calc(v) << " ";

        // solve second problem
        ll l = 1, r = 5e18;
        while(l < r) {
            ll mid = l + (r - l) / 2;
            if(calc(mid) >= k) r = mid;
            else l = mid + 1;
        }
        cout << l << "\n";
    }
}