首页 > 试题广场 >

数对

[编程题]数对
  • 热度指数：58663 时间限制：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)
算法知识视频讲解
添加回答
Python
牛客847048590号头像 牛客847048590号
链接：https://www.nowcoder.com/questionTerminal/bac5a2372e204b2ab04cc437db76dc4f?toCommentId=6246748
来源：牛客网
如果k = 0, 直接print(n*n)
否则，列一个n*n的余数表会发现每一行都会有一个循环的关系。
大于等于K的数都在K+1行及以后。
初始i = 1,每过一行i+=1
发现第K+i 行满足大于等于K的一共
1): n/(k+i)没有余数：(n//(k+i))*i
2):n//(k+i)有余数：(n//(k+i))*i+(/n%(k+i)-k+1) 
n,k = map(int,input().split())
i = 1
count = 0
if k == 0:
    print(n*n)
else:
    while k+i <= n:
        a = (n//(k+i))*i
        b = n%(k+i)
        if b < k:
            count+=a 
        if b>=k: 
            count+=(a+b-k+1)
        i+=1
    print(count)


发表于 2020-06-01 14:48:28 回复(0)
Python
午后说书人头像 午后说书人 
import sys import math
li = list(map(int,input().split(' ')))
n = li[0]
k = li[1] #余数要大于的对象 sum = 0 for i in range(k+1,n+1):
    z = int(n/i)
    t = n%i if(t>=k):
        sum = sum +z*(i-k)
        sum = sum + t-k+1  else:
        sum = sum + z * (i - k) if(k==0):
    sum = sum - n print(sum)
发表于 2020-03-29 14:30:22 回复(0)
Python
wangbo201908171423282头像 wangbo201908171423282
def solution1(n,k):
    if k==0:
        return n*n
    else:
        count=0
        for y in range(k+1,n+1):
            
            m=n//y
            l=n%y
            
            
            if l>=k:  
                s=(l-k+1)
            else:
                s=0
            count=count+(y-k)*(m)+s          
        return count
                
N=(input().split())
print(solution1(int(N[0]),int(N[1])))
发表于 2019-08-27 01:48:01 回复(0)
Python
水君201903172004868头像 水君201903172004868
余数 1 2 3 4 5 6 7 8 9 10 11 12 ...
1 0 1 1 1 1 1 1 1 1 1 1 1 ...
2 0 0 2 2 2 2 2 2 2 2 2 2 ...
3 0 1 0 3 3 3 3 3 3 3 3 3 ...
4 0 0 1 0 4 4 4 4 4 4 4 4 ...
5 0 1 2 1 0 5 5 5 5 5 5 5 ...
6 0 0 0 2 1 0 6 6 6 6 6 6 ...
7 0 1 1 3 2 1 0 7 7 7 7 7 ...
8 0 0 2 0 3 2 1 0 8 8 8 8 ...
9 0 1 0 1 4 3 2 1 0 9 9 9 ...
10 0 0 1 2 0 4 3 2 1 0 10 10 ...
11 0 1 2 3 1 5 4 3 2 1 0 11 ...
12 0 0 0 0 2 0 5 4 3 2 1 0 ...
... ... ... ... ... ... ... ... ... ... ... ... ... ...

【第一行和第一列表示索引】，上面余数矩阵（除去第一行第一列）元素Ai,j表示i%j，即取余的结果，可发现每一列都是不断循环重复的！！！！
temp = list(map(int, input().split()))
n = temp[0]
k = temp[1]
if k == 0:
    ans = n * n  # k=0是比较特殊的
else:
    ans = 0
    for y in range(k + 1, n + 1):
        # 从每一列来看，根据每y个一个循环的规律，快速计算余数矩阵余数值
        # cycle = [i for i in range(1, y)] + [0]  # 循环部分
        satisfy_num = y - k  # 一个循环中满足的组合个数
        cycle_num = n // y  # 完整循环个数
        res_num = n % y  # 剩余不完整部分循环中的元素个数
        ans += satisfy_num * cycle_num + max(res_num - k + 1, 0)  # 注意这里最差就是不完整部分满足个数为0，但是不能为负数
print(ans)
编辑于 2019-06-22 22:08:47 回复(0)
Python
Yhvx678t头像 Yhvx678t
n,k=list(map(int,input().split()))
cnt=0
for y in range(k+1,n+1):
    cnt+=n//y*(y-k)
    if n%y>=k:
        if (k):
            cnt+=n%y-k+1
        else:
            cnt+=n%y
print(cnt)

发表于 2018-07-16 21:20:26 回复(0)
Python
鲨鱼来啦头像 鲨鱼来啦
如果两次循环会产生n*n次计算
因此还需要发现其中的规律
从y入手，我们发现有以下规律：
y<k+1时，x/y的余数均小于k，因此有的取值：[k+1，n]
如n=13,k=3时：
y=[4,13],如当y=5时，符合条件的有
1 [3,5]
1 [4,5]
2 [8,5]
2 [9,5]
3 [13,5]
 我们将上述结果分两种来计算：
1）在n/y=2次循环内，x=[0-5]和x=[6-10]中分别有y-k个是余数>=k的，因此是n/y*(y-k)
2）在2次循环外，x=[11-13]，x有n%y=3种取值，其中有n%y-k+1个余数>=k；如果没有余数>=k的则count=0
因此，k!=0时，count=n/y*(y-k)+max(0,n%y-k+1) 
#coding:utf-8 import sys
line=sys.stdin.readline().split()
n=int(line[0])
k=int(line[1])
count=0 if k==0:
    count=n*n else:  for y in range(k+1,n+1):
        count+=n/y*(y-k)+max(0,n%y-k+1) print count

编辑于 2018-06-26 15:53:44 回复(0)
提交观点

问题信息

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

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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