数对
数对
http://www.nowcoder.com/questionTerminal/bac5a2372e204b2ab04cc437db76dc4f
题目难度:三星
考察点:数学、枚举
方法1:暴力算法
- 分析:
从1-n挨个枚举x,y,对于每个数对(x,y)判断是否x%y>=k,如果满足条件结果ans++,最后输出ans即可。 - 复杂度分析:
时间复杂度:O(n^2)
空间复杂度:O(1) - 代码:
#include <bits/stdc++.h> using namespace std; typedef long long LL; int main() { int n, k; cin>>n>>k; int ans = 0; for(int x=1; x<=n; x++) { for(int y=1; y<=n; y++) { if(x%y>=k) ans++; } } cout<<ans<<endl; return 0; }
方法2: 数学
分析:
由于需要满足的条件是 x%y>=k,那么y的取值范围显然属于区间[k+1, n],因为如果y<=k,一定不满足x%y>=k这个必要条件。那么我们就根据y的取值范围进行枚举,即对于每一个y来统计满足x%y>=k条件的个数,将答案记录相加即可。现在的问题是对于某个特定的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。
那么对于上述的前t个区间来说,每个小区间对y取模得到的值就是它在小区间中的下标-1,那么在小区间中找到>=k的个数就很好找了,即个数=y-k。举个例子:y=5,k=3:所以一定有如下区间存在:
[1, 2, 3, 4, 5]
那么显然x%5>=3的个数为5-3=2个,即4和5两个数,其它小区间同理。
那么一共有多少个小区间呢?显然有t=n/y个,然后我们在判断最后一个小区间中有多少个>=k的个数,显然为n%y-k+1个,当然也有可能为0个,所以两者取最大值。那么答案显然易见:对于当前枚举的y来说,有多个的x满足x%y>=k的条件。最后我们将y从k+1一直枚举到n,将每个y得到的满足条件的个数相加即可。
Tips:
(1) 需要特殊判断当k=0的情况,直接就是n*n。
(2) 注意结果需要用long long。复杂度分析:
时间复杂度:O(n)
空间复杂度:O(1)代码:
#include <bits/stdc++.h> using namespace std; typedef long long LL; int main() { int n, k; cin>>n>>k; if(k == 0) { cout<<1ll*n*n<<endl; return 0; } LL ans = 0; for(int i=k+1; i<=n; i++) { int tmp = (n-n/i*i-k+1);//n-n/i*i == n%i if(tmp < 0) tmp = 0; ans += 1ll*(i-k)*(n/i)+tmp; } cout<<ans<<endl; return 0; }
```