2018年網易實習生筆試題集合之數對

問題描述：

                整數對（x，y）x，y都不大于n ，且x%y 大于等于 k。問有多少這樣的數對。

思考：最簡單的來想 當然是雙層循環咯，但是當然複雜度太高不行。參照前面一個求餘數的問題，我們會想到是否也會有規律。

對k = 0；有n^2個

對k =1；y應該從k+1～n 在x從1～n的過程中餘數在從 0～y-1 一直做循環。

            例如此時y = 2.那麼餘數是1010101一直循環，

             y = 3. 那麼餘數120120120 一直循環。

是以找到規律。

代碼如下：

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