Hướng dẫn cho Không chia hết
Chỉ sử dụng khi thực sự cần thiết như một cách tôn trọng tác giả và người viết hướng dẫn này.
Chép code từ bài hướng dẫn để nộp bài là hành vi có thể dẫn đến khóa tài khoản.
Chép code từ bài hướng dẫn để nộp bài là hành vi có thể dẫn đến khóa tài khoản.
Authors:
Spoiler Alert
Approach Brute-forces
Hint
- Trong k số liên tiếp có \(k - 1\) số không chia hết cho \(k\) cứ thế tuần hoàn ta tìm được đáp án
Reference AC code | \(O(?) \leq O(\frac{k}{n})\) query time | \(O(1)\) auxiliary space | Brute-forces
C++
int query()
{
int n = readInt();
int k = readInt();
int pre = 0;
while (true)
{
int cur = max(0, k / n - pre);
if (cur == 0) break;
k += cur;
pre += cur;
}
cout << k << endl;
return 0;
}
Approach Binary-search
Hint
- Với mỗi số \(x\) chúng ta cần tìm \(f(x)\) là số lượng số bé hơn hoặc bằng \(x\) và không chia hết cho \(n\). Đáp án là số \(x\) nhỏ nhất thỏa mãn \(f(x) \geq k\)
Reference AC code | \(O(\log k)\) query time | \(O(1)\) auxiliary space | Binary-search
C++
int query()
{
int n = readInt();
int k = readInt();
int low = 0, high = 2 * k + 1;
while (low <= high) {
int mid = low + (high - low) / 2;
if (k <= 1LL * (n - 1) * mid)
high = mid - 1;
else
low = mid + 1;
}
ll block = 1LL * high * n;
ll extra = k - 1LL * high * (n - 1);
cout << block + extra << eol;
return 0;
}
Approach Math
Hint
-
\(\lfloor \frac{k - 1}{n - 1} \rfloor\) là số lượng các cụm \(n - 1\) phần tử (bỏ đi các bội \(n\))
-
\(\lfloor \frac{k - 1}{n - 1} \rfloor \times n\) là vị trí đầu sau khi lấy đi các giá trị bội \(n\)
-
\(k \mod (n - 1)\) là vị trí số cần tìm so với vị trí đầu (ta lấy trên đoạn [1..n - 1] nên khi \(k \equiv 1 \pmod{n - 1}\) ta tăng lên \(n - 1\))
-
Kết quả là \(\lfloor \frac{k - 1}{n - 1} \rfloor \times n + k \mod (n - 1)\)
Reference AC code | \(O(1)\) query time | \(O(1)\) auxiliary space | Math
C++
int query()
{
int n = readInt();
int k = readInt();
int block = (k - 1) / (n - 1) * n;
int extra = k % (n - 1);
if (extra == 0) extra = n - 1;
cout << block + extra << eol;
return 0;
}
Bình luận
int kcht(int a,int b){
int k=0,kbt;
while (b>0){
if (b>a-1) kbt=a-1;
else kbt=b;
k+=kbt;
if(k%a!=0) b-=kbt;
k++;
}
return k-1;
}
Code xuất phần tử ko chia hết thứ b của a;
Brute-forces tại sao lại dùng biến là k chứ không phải n nhỉ?
Updated