首页 > 试题广场 >

数对

[编程题]数对
  • 热度指数：58617 时间限制：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)
算法知识视频讲解
添加回答
JavaScript
萌萌萌哒头像 萌萌萌哒
JavaScript(Node) 😎题目:网易-数对 
// 时间复杂度O(N)
// y =>[k+1,n] res=n/y*(y-k)
// n%i-k>=0 ? res+n%i-k+1:res
const readline = require('readline');
const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout
})
let res = 0
rl.on('line',line =>{
    let n = +line.split(' ')[0],
        k = +line.split(' ')[1]
    if(k === 0){
        res = n*n
        console.log(res)
        return
    }
    //x=[1,n] y=[k,n] 遍历y,满足条件x的总数为(n/y)*(y-k)
    for (let i = k+1; i <= n; i++) {
        let cnt = Math.floor(n/i)
        let restLen = n%i
        res += cnt * (i-k)
        restLen >=k ? res += restLen-k+1: res
    }
  console.log(res)
})


发表于 2020-02-25 19:07:32 回复(0)
JavaScript
AC手环头像 AC手环 


let [n, k] = readline().split(' ').map(d=>parseInt(d))

let counter = 0

for(let y = k+1; y <= n; y++){
    let t1 = Math.floor((n)/y) * (y-k)
    let t2 = n%y - k + 1
    t2 = t2 > 0? t2: 0
    counter += t1+t2
}

if(k === 0) counter -= n
console.log(counter)


发表于 2019-08-19 16:31:56 回复(0)
提交观点

问题信息

C++工程师 golang工程师 iOS工程师 安卓工程师 运维工程师 前端工程师 算法工程师 测试工程师 PHP工程师 网易 2019 基础数学 数学 Java工程师
来自：网易2019实习生招聘...
上传者：小小
难度：
2条回答 26813浏览

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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