Hướng dẫn giải của Bedao Mini Contest 23 - Số cô đơn

Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.

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

Bình luận

Hãy đọc nội quy trước khi bình luận.


  • 2
    L0ngg  đã bình luận lúc 21, Tháng 2, 2024, 3:33

    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ì ạ :((


    • 8
      QioCass  đã bình luận lúc 21, Tháng 2, 2024, 4:46
      • ~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  đã bình luận lúc 21, Tháng 2, 2024, 12:46

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