网易招聘笔试题--数对

题目链接： https://www.nowcoder.com/question/next?pid=9763997&qid=152611&tid=14751374

解题思路：考虑固定每个y，那么对于y=k+1,,..., n,生成的符合条件的数对共有 n / y * (y - k) + (n % y - k + 1) | (n % y > 0)。

对所有的y求和即可。特例k =0 时， ans = n * n;

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 long long n, k;
 5 
 6 int main()
 7 {
 8     long long ans = 0;
 9     scanf("%lld%lld", &n, &k);
10     if (k == 0LL)
11     {
12         printf("%lld
", n * n);
13         return 0;
14     }
15     for (long long y = k + 1; y <= n; ++y)
16     {
17         ans += n / y * (y - k);
18         if (n % y >= k)
19             ans += (n % y - k + 1);
20     }
21     printf("%lld
", ans);
22     return 0;
23 }