題目描述
牛牛以前在老師那裡得到了一個正整數數對(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;
}
}