Codeforces Round 701C

传送门：https://codeforces.com/contest/1485/problem/C

题意

$给一个x和y，求\left \lfloor \frac{a}{b}\right \rfloor =a\;mod\;b成立的个数。$ $1\leq a \leq x\;\;\;1\leq b \leq y$

思路

显然这题是围绕$\left \lfloor \frac{a}{b}\right \rfloor =a\;mod\;b.$ 没有限制的话，会有b-1个（0不存在）。

我们可以手推出$\frac{3}{2},\frac{4}{3}$都可以，并且$\frac{8}{3}$也可以。 所以$\frac{b+1}{b}=1，\frac{2(b+1)}{b}=2$等等。

所以我们得出来$\frac{k(b+1)}{b}=k=a\;mod\;b。k(b+1)\leq a$

枚举b，但是题目是有限制条件的，取min就行。

$$\sum_{i=2}^bmin(i-1,\frac{a}{i+1})$$

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

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

前半部分就等差数列求和，后半部分整除分块即可。

Code（62MS）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
##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();
}