---
# System prepended metadata

title: Codeforces 1485C Floor and Mod
tags: [math, number theory]

---

# Codeforces 1485C Floor and Mod
>https://codeforces.com/contest/1485/problem/C

## 求$\sum_{a=1}^{x} \sum_{b=1}^{y} [\lfloor \frac{a}{b} \rfloor = a \% b]$, $1 \le x, y \le 10^9$

題意是說總共有幾個(a, b)使得a除以b之商等於其餘數，(一開始以為是$\lfloor \frac{a}{b} \rfloor \equiv a \ (mod \ b)$算老半天不會算==)故有$a = kb + k$，且$1 \le k \le b-1$，考慮$k$最大時$a = k(b+1) = b^2 - 1$，因為$a$最大僅到$x$所以可知若$x$超過$b^2-1$時，$k$就只有$b-1$個，所以算的話就當$x>=b^2 \Rightarrow b <= \sqrt{x}$ 累加$b-1$就好；當$b > \sqrt{x}$ 時$k$有$\lfloor \frac{x}{b+1} \rfloor$個直接整數分塊就好。
```cpp
#include <bits/stdc++.h>
#pragma GCC optimize(3)
#define ll long long
#define pii pair<int, int>
#define pll pair<long long, long long>
#define F first
#define S second
#define endl '\n'
using namespace std;
const int inf = 0x3f3f3f3f;
int mod = 1e9 + 7;
const int N = 1e6 + 5;


void solve(){
    int x, y; cin >> x >> y;
    ll ans = 0;
    int b = 1, xx = sqrt(x);
    
    for(; b<=min(xx, y); b++){
        ans += b - 1;
    }

    int lim = min(x-1, y);
    for(int r=b; b<=lim; b=r+1){
        if(b > lim) break;
        r = min(lim, x/(x/(b+1)) - 1);
        ans += (r - b + 1) * (x / (b+1));
    }
    cout << ans << endl;
    
}


int main(){
    ios::sync_with_stdio(0); cin.tie(0);
//    freopen("input.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);
    
    int t = 1;
    cin >> t;
    while(t--)
    solve();
    return 0;
}
```

## 時間複雜度：$O(\sqrt{n})$
###### tags: `math` `number theory`