C. Floor and Mod

A pair of positive integers \( (a,b) \)  is called special if \(\lfloor \frac{a}{b} \rfloor = a \bmod b \). Here, \( \lfloor \frac{a}{b} \rfloor \)is the result of the integer division between \( a \) and \( b \), while \(a \bmod b\) is its remainder.You are given two integers \(x\) and \(y\). Find the number of special pairs \( (a,b) \) such that \(1\leq a \leq x\) and \(1 \leq b \leq y\).

The first line contains a single integer \(t\) \(1 \le t \le 100\)— the number of test cases.The only line of the description of each test case contains two integers \(x\), \(y\) (\(1 \le x,y \le 10^9\)).

For each test case print the answer on a single line.

题意

输入\(x\),\(y\)计算满足\(1\leq a \leq x\),\(1 \leq b \leq y\) 时，有几对 \( (a,b) \)满足\(\lfloor \frac{a}{b} \rfloor = a \bmod b \)

思路

\(a = k* b + k\) 我们只需要针对\(1\leq k \leq \sqrt{x}\) (因为\(k^2 < kb+k = a \leq x\))

将\(1 \leq kb+k \leq x\) 变换形式，可以得到\(b \leq x/k-1\)

所以对于一个\(k\),有\(max(0, min(y,x/k-1) - k)\)对合法答案。

代码

 1 #include<iostream>
 2 #include<cmath>
 3 #include<algorithm>
 4 using namespace std;
 5 using ll = long long;
 6 inline int read()
 7 {
 8     int X = 0; bool flag = 1; char ch = getchar();
 9     while (ch < ‘0‘ || ch>‘9‘) { if (ch == ‘-‘) flag = 0; ch = getchar(); }
10     while (ch >= ‘0‘ && ch <= ‘9‘) { X = (X << 1) + (X << 3) + ch - ‘0‘; ch = getchar(); }
11     if (flag) return X;
12     return ~(X - 1);
13 }
14 void solve()
15 {
16     ll x, y;
17     x = read();
18     y = read();
19     ll ans = 0;
20     ll k;
21     for (k = 1; k * k <= x; k++)
22     {
23         ans += max(0LL, min(y, x / k - 1) - k);
24     }
25     cout << ans << "\n";
26 }
27 int main()
28 {
29     ios::sync_with_stdio(false);
30     cin.tie(0);
31     int t;
32     t = read();
33     while (t--)
34     {
35         solve();
36     }
37     return 0;
38 }

参考思路

https://codeforces.com/blog/entry/87470

第一次在博客园上用数学公式，果然还是不熟练啊..折腾了好久。排版有点乱，见谅。

CF1485C Floor and Mod

原文：https://www.cnblogs.com/iceyz/p/14401198.html