数对

数对

http://www.nowcoder.com/questionTerminal/bac5a2372e204b2ab04cc437db76dc4f

题目难度:三星
考察点:数学、枚举

方法1:暴力算法

  1. 分析:
    从1-n挨个枚举x,y,对于每个数对(x,y)判断是否x%y>=k,如果满足条件结果ans++,最后输出ans即可。
  2. 复杂度分析:
    时间复杂度:O(n^2)
    空间复杂度:O(1)
  3. 代码:
    #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: 数学

  1. 分析:
    由于需要满足的条件是 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]
    [2
    y+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。

  2. 复杂度分析:
    时间复杂度:O(n)
    空间复杂度:O(1)

  3. 代码:

    #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;
    }
    

```

全部评论

相关推荐

10-30 10:16
南京大学 Java
龚至诚:给南大✌️跪了
点赞 评论 收藏
分享
3 收藏 评论
分享
牛客网
牛客企业服务