veteran233QAQ的博客
0%

Codeforces Round 701 - C - Floor and Mod

发表于 更新于

题目

https://codeforces.com/contest/1485/problem/C

思路

由$1\leq a\leq x,1\leq b\leq y,\lfloor\frac{a}{b}\rfloor=a\bmod b$得：
$\lfloor\frac{a}{b}\rfloor=a \bmod b=a-\lfloor\frac{a}{b}\rfloor b$
$\lfloor\frac{a}{b}\rfloor=\frac{a}{b+1}$
由于$\lfloor\frac{a}{b}\rfloor$为整数，所以$b+1$必定整除$a$，即$a \bmod (b+1)=0$
令$a=n(b+1) \leq x$，则
$\lfloor\frac{a}{b}\rfloor=\lfloor\frac{n(b+1)}{b}\rfloor=\lfloor n+\frac{n}{b}\rfloor=n+\lfloor\frac{n}{b}]$
结合上述得：$\lfloor\frac{n}{b}\rfloor=0$
由于$n>0$，所以$b>n$，结合b的范围得：

  1. $b>n$
  2. $n(b+1) \leq x$
  3. $1 \leq b \leq y$

考虑第二个范围对存在的$b$适用，所以左边取最小值，即$n(n+2)\leq x$
接着枚举$n$，则$n<b\leq\min(\frac{x}{n}-1,y)$

$b$的个数为$\min(\frac{x}{n}-1,y)-n$（注意这里没有考虑$n>\min(\frac{x}{n}-1,y)$，可以用一个max解决）

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <bits/stdc++.h>
#define endl '\n'
#define lson(x) (x<<1)
#define rson(x) (x<<1|1)
#define lowbit(x) (x&-x)
using namespace std;
struct _IO { _IO() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); } }_io;
typedef long long ll; typedef unsigned long long ull; typedef long double ld; typedef pair<ll, ll> pll;

int main()
{
    ll T;
    cin >> T;
    while (T--)
    {
        ll x, y, ans = 0;
        cin >> x >> y;
        for (ll n = 1; n * (n + 2) <= x; ++n) ans += max(min(x / n - 1, y) - n, 0ll);
        cout << ans << endl;
    }
    return 0;
}