数对

题目难度：三星
考察点：数学、枚举

方法1：暴力算法

1. 分析：
   从1-n挨个枚举x,y，对于每个数对(x,y)判断是否x%y>=k，如果满足条件结果ans++，最后输出ans即可。
2. 复杂度分析：
   时间复杂度：O(n^2)
   空间复杂度：O(1)
3. 代码：

   #include <bits/stdc++.h>
   using namespace std;
   typedef long long LL;
   int main() {
    int n, k; cin>>n>>k;
    int ans = 0;
    for(int x=1; x<=n; x++) {
        for(int y=1; y<=n; y++) {
            if(x%y>=k) ans++;
        }
    }
    cout<<ans<<endl;
    return 0;
   }

方法2： 数学

1. 分析：
   由于需要满足的条件是 x%y>=k，那么y的取值范围显然属于区间[k+1, n]，因为如果y<=k，一定不满足x%y>=k这个必要条件。那么我们就根据y的取值范围进行枚举，即对于每一个y来统计满足x%y>=k条件的个数，将答案记录相加即可。现在的问题是对于某个特定的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。
   那么对于上述的前t个区间来说，每个小区间对y取模得到的值就是它在小区间中的下标-1，那么在小区间中找到>=k的个数就很好找了，即个数=y-k。举个例子：y=5，k=3：所以一定有如下区间存在:
   [1, 2, 3, 4, 5]
   那么显然x%5>=3的个数为5-3=2个，即4和5两个数，其它小区间同理。
   那么一共有多少个小区间呢？显然有t=n/y个，然后我们在判断最后一个小区间中有多少个>=k的个数，显然为n%y-k+1个，当然也有可能为0个，所以两者取最大值。那么答案显然易见：对于当前枚举的y来说，有多个的x满足x%y>=k的条件。最后我们将y从k+1一直枚举到n，将每个y得到的满足条件的个数相加即可。
   Tips：
   (1) 需要特殊判断当k=0的情况，直接就是n*n。
   (2) 注意结果需要用long long。

2. 复杂度分析：
   时间复杂度：O(n)
   空间复杂度：O(1)

3. 代码：

   #include <bits/stdc++.h>
   using namespace std;
   typedef long long LL;
   int main() {
    int n, k; cin>>n>>k;
    if(k == 0) {
        cout<<1ll*n*n<<endl;
        return 0;
    }
    LL ans = 0;
    for(int i=k+1; i<=n; i++) {
        int tmp = (n-n/i*i-k+1);//n-n/i*i == n%i
        if(tmp < 0) tmp = 0;
        ans += 1ll*(i-k)*(n/i)+tmp;
    }
    cout<<ans<<endl;
    return 0;
   }
   

```