Codeforces 1485C - Floor and Mod (設計解題、數學推理)

題目大意

有一種特殊的 pair(A,B)，定義這種 pair 必須符合 \([ \frac{a}{b} ] = a \ mod \ b\)

給你一個數字 x,y，其中特殊的 pair 數值必須是 \(1 \leq x \leq a \)、\(1 \leq y \leq b\)，告訴我在這個範圍內有多少這種 pair 的數量。

題目連結

重點觀念

• 數學邏輯推理
• 時間複雜度推測

分析：

這題有難度XD，我被考倒了QQ。稍微看了下題目發現這是移項問題，只要移項移好腦袋清楚就可以把它成功解出了！

這題的 x,y 都是 \(10^9\)，有點刺激阿，由於 \(O(N) = 10^8\)，因此似乎這題時間複雜度要比 \(O(n)\) 還小。

codeforec 有很多人教學，在看了多遍後，能將這些話給講出來。

StepA 推出 K 的範圍:

我們可以定義 \( a \ mod \ b \) 出來的值為 k，因此 \([ \frac{a}{b} ] = a \ mod \ b = k\)

稍微進行移項，\( a = bk + k\)，其中 \(b > k\)，否則不符合 \( [ \frac{a}{b} ] = k \)

再來我們稍微進行粗略分析，\(bk+k > k^2\)，我們前面有提到 \(b > k\)，我們把所有的數學推導都拉出來寫寫看。

\(x \geq a = bk + k \geq k^2 \)，再來我們進行約分，收斂下後就可以得到 \(k \leq \sqrt{x}\)

StepB 找出 b 的範圍:

現在我們可以知道有特殊的 pair，範圍只在 \(1 \leq k \leq \sqrt{x}\) 、\(b > k\)、 \(1 \leq kb+k \leq x\)，\(kb+k\) 是 \([\frac{a}{b}] = k\) 的移項。

再來我們進行推導，就可以將 \(1 \leq kb+k \leq x\) 推成 \(1 \leq b \leq x\k-1\)，同除 k，但 1 不變動，因為題目要求最小值是 1。

StepC 找出公式

再來我們可以推出一個算式，\(min(y,x/k-1) - k\)，我們這邊是在找有哪些 b 可以用，而不是再找有哪些方式 k 會符合，透過找有幾個 b 可以用來算出答案。

StepB 有說到 \(1 \leq b \leq x\k-1\)，但 y 不一定會小於 \(x\k-1\) 也不一定大於，因此特別用個 min 來找出最小值，找出最小的值。這裡是公式最重要最需要注意的地方。

減 k 則是 Step1 有說到，b 必須要大於 k，否則不滿足。

參考連結

Editorial of Codeforces Round #701 (Div. 2) - Codeforces By TheScrasse
codeforces 1485 C Floor and Mod (枚举+推导) - CSDB by (xsj)

心得

這題真的很讚。

有好多的邏輯推導是我沒有被訓練過的，一時都沒有辦法學起來。老實講我沒有把握我現在就把這些都吸收完成，但我相信只要我多練習幾次，一定可以把這些問題都解開。

我希望我能夠成為一位優秀的解題大師，可以解出所有的問題。

題目程式碼

會在下面放一些簡單註解，供大家學習時參考。

#include <iostream>
#include <bits/stdc++.h>
#define LOCAL
#define MAXN 1e10 //題目最大值
#define int long long //用 long long 才不會 i*i 無法被 int 記下
using namespace std;
int x, y, n, ans;

int32_t main()
{
#ifdef LOCAL
    freopen("in1.txt", "r", stdin);
#endif // LOCAL
    cin >> n;
    while(n--){
        cin >> x >> y; //輸入資料
        ans = 0;
        for(int i = 1; i*i < x; i++) ans += max(0ll, min(x/i-1, y) - i);
        //k 要小於 sqrt x，這裡的 k 是 i，再配合公式就可以得出答案
        cout << ans << "\n";
    }
    return 0;
}