数对

题目：

牛牛以前在老师那里得到了一个正整数数对(x, y), 牛牛忘记他们具体是多少了。

但是牛牛记得老师告诉过他x和y均不大于n, 并且x除以y的余数大于等于k。

牛牛希望你能帮他计算一共有多少个可能的数对。

输入描述：

输入包括两个正整数n,k。

输出描述：

对于每个测试用例, 输出一个正整数表示可能的数对数量。

样例：

in:
5 2

out:
7

因为x%y==k，则y的取值范围为(k,n]，则y确定时，x在其区间【0，n】内可取（n/y）个模等价区间，其中有y-k个值符合x的定义。则有（n/y）*（y-k）个。

在最后一段区间n%y中，若n%y>=k,则有n%y-k+1个值符合，故sum+=(n/y)*(y-k)+(n%y>=k?n%y-k+1:0);

当k==0时，x，y可取n内任一值，故有n*n种。

AC代码：

1 #include<bits/stdc++.h>
 2 using namespace std;
 3 
 4 int main(){
 5     long long n,k;
 6     cin>>n>>k;
 7     long long sum=0;
 8     if(k==0){
 9         sum=n*n;
10     }
11     else{
12         for(long long i=k+1;i<=n;i++){
13             sum+=(n/i)*(i-k)+(n%i>=k?n%i-k+1:0);
14         }
15     }
16     cout<<sum<<endl;
17     return 0;
18 }

原文链接: https://www.cnblogs.com/Kiven5197/p/8718253.html

欢迎关注

微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍