天天看點

數對(網易校招)

題目描述

牛牛以前在老師那裡得到了一個正整數數對(x, y), 牛牛忘記他們具體是多少了。

但是牛牛記得老師告訴過他x和y均不大于n, 并且x除以y的餘數大于等于k。

牛牛希望你能幫他計算一共有多少個可能的數對。

輸入描述:

輸入包括兩個正整數n,k(1 <= n <= 10^5, 0 <= k <= n - 1)。

輸出描述:

對于每個測試用例, 輸出一個正整數表示可能的數對數量。

示例1

輸入

5 2

輸出

7

思路:計算大mod小,小mod大即可,注意除 k 算周期時的剩餘情況和特判0

#include<bits/stdc++.h>
 #define ll long long
  using namespace std;
    int main()
    {
       ll n , k;
        while(cin >> n >> k)
          if(k >= n) cout << 0 << endl;
          else{
              if(k == 0)
              {
                   cout << n * n << endl;
                   continue;
              }
               ll a = n - k;
               ll smb = (a + a * a)/2;
               ll bms = 0;
               ll it = 1;
               ll k1 = k;
               for(++k;k<n;++k,++it)
                {
                  ll gps = (n-k+1) / k * it;
                  if(n % k >= k1 && n % k < k - 1)
                  {
                     gps += ( n % k ) - k1 + 1;
                  }
                  bms += gps;
                }

               cout << smb + bms << endl;
          }
    }

           

繼續閱讀