题目描述
牛牛以前在老师那里得到了一个正整数数对(x, y), 牛牛忘记他们具体是多少了。

但是牛牛记得老师告诉过他x和y均不大于n, 并且x除以y的余数大于等于k。
牛牛希望你能帮他计算一共有多少个可能的数对。

输入描述:
输入包括两个正整数n,k(1 <= n <= 10^5, 0 <= k <= n - 1)。
输出描述:
对于每个测试用例, 输出一个正整数表示可能的数对数量。
示例1
输入
复制
5 2
输出
复制
7
说明
满足条件的数对有(2,3),(2,4),(2,5),(3,4),(3,5),(4,5),(5,3)

这题绝对是某个大厂的第一道编程题,考数学的。
若直接暴力枚举时间复杂度为O(n^2),不能接受
分析,对于除数y,肯定要大于等于k,不然x%y肯定小于等于k,再来看被除数x
当对于一个被除数确定,此时遍历一遍x。

现在的问题是对于某个特定的y如何计算满足条件的个数,由于x属于[1,n]区间,我们在将其划分为若干个小区间如下:
[1, 2, ..., y]
[y+1, y+2, ..., 2y]
[2y+1, 2y+2, ..., 3y]
...
[ty+1, ty+2, ..., n]
其***有t=n/y个小区间,在每个区间内有y-k个元素其x%y大于等于k。
对于最后一个区间,其大于k的元素数量为y%k-k+1个,当然这个数字可能小于0,所以要进行一个比较

#include<iostream>
#include<math.h>
using namespace std;

int main(){
    int n,k;
    cin >> n >> k;
    if(k == 0){
        cout << (long long)n * (long long)n << endl;
        return 0;
    }
    long long res = 0;
    for(int y=k;y<=n;y++){
        res += (n/y)*(y-k) + max(n%y-k+1,0);
    }
    cout << res << endl;
    return 0;
}