Codeforces Round #701 (Div. 2) C. Floor and Mod （數學/思維/整除分塊）

折躍坐標：https://codeforces.com/contest/1485/problem/C

題面：

題目大意：
（下文中 a b \frac ab ba?均為向下取整）
給你一個x，y (1 ≤ x, y ≤ 10e9)
問有多少個(a，b)滿足 a b = a m o d b ( 1 ≤ a ≤ x , 1 ≤ b ≤ y ) \frac ab = a\quad mod \quad b \quad (1 ≤ a ≤ x,1 ≤ b ≤ y) ba?=amodb(1≤a≤x,1≤b≤y)

數學思路：

設 a b = k \frac ab=k\quad ba?=k， a m o d b = m a\quad mod \quad b = m amodb=m
得 k ? b + m = a k*b+m=a k?b+m=a， 其中 k = m k = m k=m
整理得到 k ? ( b + 1 ) = a ( b > k ) k*(b+1)=a\quad(b>k) k?(b+1)=a(b>k)
由此，我們的任務轉變為找到對于每個b 有多少個k滿足 k ? ( b + 1 ) = a ( b > k ) k*(b+1)=a\quad(b>k) k?(b+1)=a(b>k)
因為有 1 ≤ a ≤ x a n d k < b 1 ≤ a ≤ x \quad and \quad k < b 1≤a≤xandk<b
可以得到 k = m i n ( b ? 1 , x b + 1 ) k = min(b-1,\frac{x}{b+1}) k=min(b?1,b+1x?)
接下來，我們希望知道一個關于k的分段函式
b ? 1 < x b + 1 b-1 <\frac{x}{b+1} b?1<b+1x?
( b + 1 ) ? ( b ? 1 ) < x (b+1)*(b-1)<x (b+1)?(b?1)<x
b 2 ? 1 < x b^2 -1 < x b2?1<x
b 2 < x + 1 b^2 < x + 1 b2<x+1
b < x + 1 b < \sqrt{x+1} b<x+1 ?
所以
k = b ? 1 ( b < x + 1 ) k = b-1\quad(b < \sqrt{x+1}) k=b?1(b<x+1 ?)
k = x b + 1 ( b > x + 1 ) k = \frac{x}{b+1}\quad(b > \sqrt{x+1}) k=b+1x?(b>x+1 ?)
對于 ( b < x + 1 ) (b < \sqrt{x+1}) (b<x+1 ?)的部分，因為比較少，可以直接列舉，也可以直接用等引數列公式求和
對于 ( b > x + 1 ) (b > \sqrt{x+1}) (b>x+1 ?)的部分，我們則需要用整除分塊的知識解決
關于整除分塊，對于這道題，我們只需要簡單地知道，
在 n i , n i + 1 . . . . . . \frac ni,\frac{n}{i+1}...... in?,i+1n?......這樣的式子中，最大的,滿足 n i = n j \frac ni = \frac nj in?=jn?的 j j j = n n i \frac{n}{\frac ni} in?n?
對于連續的 n i , n i + 1 . . . . . . n j \frac ni,\frac{n}{i+1}......\frac nj in?,i+1n?......jn?的和 等同于 ( j ? i + 1 ) ? n i (j-i+1)*\frac ni (j?i+1)?in?

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;
}