题目描述
牛牛以前在老师那里得到了一个正整数数对(x, y), 牛牛忘记他们具体是多少了。
但是牛牛记得老师告诉过他x和y均不大于n, 并且x除以y的余数大于等于k。
牛牛希望你能帮他计算一共有多少个可能的数对。
输入描述:
输入包括两个正整数n,k(1 <= n <= 10^5, 0 <= k <= n - 1)。
输出描述:
对于每个测试用例, 输出一个正整数表示可能的数对数量。
示例1
输入
复制
5 2
输出
复制
7
说明
满足条件的数对有(2,3),(2,4),(2,5),(3,4),(3,5),(4,5),(5,3)
这题绝对是某个大厂的第一道编程题,考数学的。
若直接暴力枚举时间复杂度为O(n^2),不能接受
分析,对于除数y,肯定要大于等于k,不然x%y肯定小于等于k,再来看被除数x
当对于一个被除数确定,此时遍历一遍x。
现在的问题是对于某个特定的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个小区间,在每个区间内有y-k个元素其x%y大于等于k。
对于最后一个区间,其大于k的元素数量为y%k-k+1个,当然这个数字可能小于0,所以要进行一个比较
#include<iostream> #include<math.h> using namespace std; int main(){ int n,k; cin >> n >> k; if(k == 0){ cout << (long long)n * (long long)n << endl; return 0; } long long res = 0; for(int y=k;y<=n;y++){ res += (n/y)*(y-k) + max(n%y-k+1,0); } cout << res << endl; return 0; }