Editorial for Bedao Mini Contest 23 - Số cô đơn
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
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ì ạ :((
dạ em cám ơn nhiều ạ <3