折跃坐标:https://codeforces.com/contest/1485/problem/C

题面:
在这里插入图片描述

题目大意:
(下文中$\frac ab$均为向下取整)
给你一个x,y (1 ≤ x, y ≤ 10e9)
问有多少个(a,b)满足$\frac ab = a\quad mod \quad b \quad (1 ≤ a ≤ x,1 ≤ b ≤ y)$

数学思路:

设 $\frac ab=k\quad$,$a\quad mod \quad b = m$
得$kb+m=a$, 其中$k = m$
整理得到$k
(b+1)=a\quad(b>k)$
由此,我们的任务转变为找到对于每个b 有多少个k满足$k*(b+1)=a\quad(b>k)$
因为有$1 ≤ a ≤ x \quad and \quad k < b$
可以得到$k = min(b-1,\frac
{b+1})$
接下来,我们希望知道一个关于k的分段函数
$b-1 <\frac
{b+1}$
$(b+1)(b-1)<x$
$b2 -1 < x$
$b
2 < x + 1$
$b < \sqrt{x+1}$
所以
$k = b-1\quad(b < \sqrt{x+1})$
$k = \frac
{b+1}\quad(b > \sqrt{x+1})$
对于$(b < \sqrt{x+1})$的部分,因为比较少,可以直接枚举,也可以直接用等差数列公式求和
对于$(b > \sqrt{x+1})$的部分,我们则需要用整除分块的知识解决
关于整除分块,对于这道题,我们只需要简单地知道,
在$\frac ni,\frac
{i+1}......$这样的式子中,最大的,满足$\frac ni = \frac nj$的$j$ = $\frac{\frac ni}$
对于连续的$\frac ni,\frac
{i+1}......\frac nj$的和 等同于 $(j-i+1)
\frac ni$

ac代码:

#include <iostream>
#include <queue>
#include <stack>
#include <algorithm>
#include <vector>
#include <string>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <climits>
#define Buff std::ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define ll long long
#define inf LONG_LONG_MAX
#define Inf INT_MAX

using namespace std;

const int Maxn = 1e7 + 10;
const ll Mod = 1e9 + 7;
ll x, y;
ll ans;
int t;
int main()
{
    Buff;
    cin >> t;
    while (t--)
    {
        ans = 0;
        cin >> x >> y;
        for (ll b = 2; b <= min(y, (ll)sqrt(x + 1)); b++)
            ans += b - 1;
        ll l, r;
        for (l = sqrt(x + 1) + 1; l <= min(x, y); l = r + 1)
        {
            if (x / (l + 1) <= 0) 
                break;
            r = min(y, min(x, x / (x / (l + 1))-1));
            //这里-1的原因是:除的是l+1而不是l
            ans += (r - l + 1) * (x / (l + 1));
        }
        cout << ans << endl;
    }
    return 0;
}