Editorial for Bedao Mini Contest 23 - Số cô đơn

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

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";
    }
}

Comments

Please read the guidelines before commenting.

2

L0ngg commented on Feb. 21, 2024, 3:33 a.m.

Cho em hỏi xíu ạ, tại sao chỉ cần quan tâm đến các số 2, 3, 5, 7 mà kh phải 9 giá trị, mà 9 giá trị ở đây là gì ạ :((

7
QioCass commented on Feb. 21, 2024, 4:46 a.m.
~9~ giá trị ở đây là các số từ ~2~ tới ~10~.

Còn tại sao lại chỉ quan tâm tới ~2, 3, 5, 7~ mà không phải cả ~9~ giá trị? Thì...

Như đã nói số cô đơn là số không chia hết cho các số từ ~2~ tới ~10~.

Do đó ta chỉ cần quan tâm số mình cần xét có chia hết một trong các số nguyên tố từ ~2~ tới ~10~ hay không mà thôi.

Để giải thích tại sao không quan tâm tới các số không nguyên tố khác thì ta lấy ví dụ số ~6~.

Nếu số mình xét chia hết cho ~6~, thì chắc chắn nó chia hết cho ~2, 3~. Do đó chỉ cần kiểm tra ~2, 3~ là đủ. Tương tự với các số không nguyên tố còn lại.

2

L0ngg commented on Feb. 21, 2024, 12:46 p.m.

dạ em cám ơn nhiều ạ <3