网易2018春招笔试编程题——nk数对

￡神魔★判官ぃ 2022-05-28 06:20 284阅读 0赞

题目描述：

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

但是牛牛记得老师告诉过他x和y均不大于n, 并且x除以y的余数大于等于k。

牛牛希望你能帮他计算一共有多少个可能的数对。

![70][]

首先用两个for循环来暴力求解是可以得到结果，但是时间复杂度太高。所以需要从数学的角度分析，寻找新的思路。

1.首先分析数对的右边的数。x%y的余数，其余数的范围必定为\[0—y-1\]，所以为了满足余数大于等于k，这个y必须为k+1或者更大，x%y的余数才可能出现k。

2.题目明确为正整数数对，分析x%y与其余数的关系。可以其余数是循环出现的。

对于一个b, n范围内的数模b的序列应该是:

0,1,2,...,b-1, 0, 1, 2,..., b-1,...0,1,2,..n%b

比如b为3，n为1-10.

![70 1][]由这个例子，我们可以看出来，1,2,0循环出现，完整出现的循环有3次，剩下可能有一次不完整的循环。

可知，完整循环次数为3/10，不完整循环的长度为3%10，不管是哪种，都是从1开始的。

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

程序分析：

1.for 循环中i变量就是数对的右边的数

2.对于数对的右边的数为i的这些数对，只需要分析两种情况，完整循环和不完整循环

3.分析完整循环：循环次数为n/i。因为\[0—i-1\]是余数的范围(但实际出现顺序为0在结尾)，也是循环的范围，排除前k个数（想象从0开始排除），那么剩下的余数肯定是大于等于k的。

4.分析不完整循环：只有一次，但长度不定。长度为n%i。分析上面的例子，发现其余数范围为\[1,2,3,,,,n%i\]，也是实际出现顺序。所以排除前k-1个数（和上面不同的是，这里是从1开始的，所以只需要排除k-1个数），那么剩下的余数都是大于等于k的。所以if的判断条件为n%i>=k，因为这样刚好最后一个余数为k。

[70]: /images/20220528/d52cba1deaaf4c20a0bd34cd4249ab34.png
[70 1]: /images/20220528/2c4040f3c53f4fea96ac745514e148da.png