首页 > 试题广场 >

数对

[编程题]数对
  • 热度指数：502 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
  • 算法知识视频讲解

牛牛以前在老师那里得到了一个正整数数对(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)
算法知识视频讲解
添加回答
GooHub头像 GooHub 
if __name__ == '__main__':
    # 解析参见https://blog.csdn.net/anlian523/article/details/79763170
    # 输入
    n, k = list(map(int, input().split()))
    if k == 0:
        print(n * n)
    else:
        count = 0
        for y in range(k+1,n+1):
            # 分出完整循环部分和不完整循环部分
            count += (n // y) * (y - k)
            # 这部分是最后一部分（最后一部分一定要出现余数大于等于k的情况才会统计）
            if n % y >= k:
                count += (n % y) - k + 1
        print(count)

发表于 2018-08-05 11:48:50 回复(0)
Stream201908251425680头像 Stream201908251425680 
* 思路 x<=n ；y<=n ；x%y>=k 
public class dataque { public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in); long n= scanner.nextLong(); long k= scanner.nextLong(); int dataqueNum=0; if (1 <= n&&n <= 10*10*10*10*10&&k>=0&&k<=n-1) { for (int x = 1; x <= n; x++) { for (int y= 1; y <= n; y++) { if (x%y >=k) {
                        dataqueNum+=1;
                    }
                }
            }
            System.out.println(dataqueNum);
        }

    }
}

发表于 2019-08-27 01:52:39 回复(0)
&pipemm头像 &pipemm
x%y的余数，x的范围必定为[0,y-1]，为了满足余数大于等于k，y必须为k+1或者更大，x%y的余数才可能出现k。
每个长度为y的段中，都有k个数（[my+1,my+k)）除以y的余数是小于k的，则这一段中余数大于等于k的有y-k个。
完整循环次数为 n/i ， 非完成循环次数为 n%i
编辑于 2019-08-13 20:44:47 回复(0)
香蕉皮233头像 香蕉皮233
import java.util.Scanner;
public class Main {
    public static void main(String args[]) {
        Scanner scan = new Scanner(System.in);
        long n = scan.nextLong();
        long k = scan.nextLong();
        long count = 0;
        if (k == 0) {
            System.out.println(n * n);}//k为0的话直接就是n的平方
        else{
        for (long i = k + 1; i <= n; i++) {
            count += (n / i) * (i - k);//找前(n / i * i)个数里面有几个循环节，每一个节有(i - k)个数
            if (n % i >= k) {
                count += n % i - k + 1;//剩下的数不足一个循环节，找第(n / i * i + 1 , n)里面有几个数满足题
            }
        }
       System.out.println(count);
    }
    }
}
发表于 2018-07-16 10:04:46 回复(0)
提交观点

问题信息

C++工程师 iOS工程师 安卓工程师 运维工程师 前端工程师 网易 算法工程师 2018 PHP工程师 数学 大数据开发工程师 Java工程师
上传者：小小
难度：
4条回答 2057浏览

热门推荐

通过挑战的用户

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号