Codeforces Round #701 C. Floor and Mod 數學推導

題意

給 一 個 x 和 y ， 求 ? a b ? = a ?? m o d ?? b 成 立 的 個 數 ， 給一個x和y，求\left \lfloor \frac{a}{b}\right \rfloor =a\;mod\;b成立的個數， 給一個x和y，求?ba??=amodb成立的個數，
1 ≤ a ≤ x ?????? 1 ≤ b ≤ y 1\leq a \leq x\;\;\;1\leq b \leq y 1≤a≤x1≤b≤y

思路

顯 然 這 題 是 圍 繞 ? a b ? = a ?? m o d ?? b . 顯然這題是圍繞\left \lfloor \frac{a}{b}\right \rfloor =a\;mod\;b. 顯然這題是圍繞?ba??=amodb.
沒 有 限 制 的 話 ， 會 有 b ? 1 個 （ 0 不 存 在 ） ， 沒有限制的話，會有\red{b-1}個（0不存在）， 沒有限制的話，會有b?1個（0不存在），

我 們 可 以 手 推 出 3 2 , 4 3 都 可 以 ， 并 且 8 3 也 可 以 ， 我們可以手推出\frac{3}{2},\frac{4}{3}都可以，并且\frac{8}{3}也可以， 我們可以手推出23?,34?都可以，并且38?也可以，
所 以 b + 1 b = 1 ， 2 ( b + 1 ) b = 2 等 等 ， 所以\frac{b+1}{b}=1，\frac{2(b+1)}{b}=2等等， 所以bb+1?=1，b2(b+1)?=2等等，

所 以 我 們 得 出 來 k ( b + 1 ) b = k = a ?? m o d ?? b ， k ( b + 1 ) ≤ a 所以我們得出來\frac{k(b+1)}{b}=k=a\;mod\;b，\red{k(b+1)\leq a} 所以我們得出來bk(b+1)?=k=amodb，k(b+1)≤a

枚 舉 b ， 但 是 題 目 是 有 限 制 條 件 的 ， 取 m i n 就 行 ， 列舉b，但是題目是有限制條件的，取min就行， 枚舉b，但是題目是有限制條件的，取min就行，

∑ i = 2 b m i n ( i ? 1 , a i + 1 ) \sum_{i=2}^bmin(i-1,\frac{a}{i+1}) i=2∑b?min(i?1,i+1a?)

首 先 要 算 一 下 中 間 值 i ? 1 = a i + 1 , i = a + 1 ， 最 后 得 ： 首先要算一下中間值i-1=\frac{a}{i+1},i=\sqrt{a+1}，最后得： 首先要算一下中間值i?1=i+1a?,i=a+1 ?，最后得：

∑ i = 2 a + 1 i ? 1 + ∑ i = a + 1 + 1 b a i + 1 \sum_{i=2}^{\sqrt{a+1}}i-1+\sum_{i=\sqrt{a+1}+1}^b\frac{a}{i+1} i=2∑a+1 ??i?1+i=a+1 ?+1∑b?i+1a?

前 半 部 分 就 等 差 數 列 求 和 ， 后 半 部 分 整 除 分 塊 即 可 ， 前半部分就等引數列求和，后半部分整除分塊即可， 前半部分就等差數列求和，后半部分整除分塊即可，

Code（62MS）

#include "bits/stdc++.h"
 using namespace std;
 
typedef long long ll;
 
 
void solve() {
 
    int _; cin >> _;
    while(_--) {
        ll a, b; cin >> a >> b;
        ll ans = 0;
        ll t = sqrt(a + 1);
        if(t > b) {
            t = b;
            ans += t * (t - 1) / 2;
        }
        else {
            ans += t * (t - 1) / 2;
            for (ll l = t + 1, r; l <= min(a, b); l = r + 1) {
                if (a / (l + 1) == 0) break;
                else r = min(b, min(a, a / (a / (l + 1)) - 1));
                ans += (r - l + 1) * (a / (l + 1));
            }
        }
        cout << ans << endl;
    }
}
 
signed main() {
    solve();
}