我要招人

去企业版

首页 > 试题广场 >

数对

[编程题]数对

热度指数：1112 时间限制：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

输出

说明

满足条件的数对有(2,3),(2,4),(2,5),(3,4),(3,5),(4,5),(5,3)

算法知识视频讲解

C/C++

tinanoro

C++的数据溢出问题还真是烦。把n的类型设为long long, 编译时还是会警告n*n，会有溢出。幸好这里是平方，可以用pow(n,2)。要是下回真的是两个不算太大的数相乘，还真是没有办法了。哪路大神可以告诉我该怎么解决这个问题

#include<bits/stdc++.h>

using namespace std;
int main() {
long int n;
long int k;
cin >> n >> k;
long long count = 0;
if (k == 0) {
count += pow(n, 2);
}
else {
for(long int y = k + 1; y <= n; y++) {
count += (n/y) * (y - k);
if (n % y >= k) {
count += n % y - k + 1;
}
}
}
cout << count << endl;
}

发表于 2018-08-17 22:49:27 回复(3)

abcabcabc

n,k = map(int, input().split())
result = 0
if(k == 0):
print(n*n)
else:
for chushu in range(k+1, n+1):
result = result + (chushu - k)*(n // chushu)
if (n % chushu) >= k:
result = result + (n % chushu) - k + 1
print(result)

发表于 2018-08-17 17:15:38 回复(0)

鹏123

import sys

if __name__ == '__main__':
line = sys.stdin.readline().strip()
values = list(map(int,line.split()))
n,k = values[0],values[1] # 5 2
# print(n,k)
sum_ = 0
x = k
while x<n+1:
y = x+1
if x >= k:
sum_ += n-x
y = k
while y < x+1:
if x%y >=k:
sum_ += 1
y += 1
x += 1
print(sum_)

发表于 2018-08-14 10:16:06 回复(0)

猫呜呜

//直接根据题意，两层循环即可。x y的初值和递进可以稍加优化

#include <iostream>

using namespace std;
int findNumberOfPairs(int n, int k){
    int cnt = 0;
    for (int y = 2; y <= n - k; ++y){
        for (int x = y + k; x <= n; ++x){
            int R = x / y;
            if (x - y*R >= k){
                ++cnt;
                continue;
            }
        }
    }
    return cnt;
}

int main(){
    cout<< findNumberOfPairs(10, 2);

return 0;

}

编辑于 2018-08-11 12:26:53 回复(0)

屋檐下雨

def findTuples(n, k):

count = 0

# 因为x除以y的余数大于k，所以y的取值范围只能是 [k+1, n]

for y in range(k + 1, n + 1):

# x除以y的余数肯定小于y，所以余数的取值范围是[k, y]

for j in range(k, y):

# con 为x除以y后的整数商

con = 0

# 找到所有满足 x <= n 的情况（其中x = con * y + j ）

while y * con + j <= n:

# 打印出来满足的结果

# 如果这里不用打印的话，可以不用这个while循环，

# 直接算出最大的con，然后count += (con + 1)即可

print(y * con + j , y)
count += 1
con += 1
return count

发表于 2018-06-08 10:58:31 回复(2)

多吃水果抵抗电脑辐射

import java.util.Scanner;
public class Main{
public static void main(String[] args){
    Scanner sc=new Scanner(System.in);
    long n=sc.nextLong();
    long k=sc.nextLong();
    long count=0;
    long u,v;//u记录在模等价区间内的数对个数；v记录在最后一段的数对个数
    if(k==0){
        count=n*n;
    }else{
        for(long y=k+1;y<=n;y++){
             u=(n/y)*(y-k);
             v=(n%y)>=k?(n%y-k+1):0;
             count+=u+v;
        }
    }
    System.out.println("共有："+count+"个数对");
}
}

发表于 2018-06-08 09:18:20 回复(0)