首页 > 试题广场 >

数对

[编程题]数对

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

算法知识视频讲解

求天求地求Offer

import java.util.*;
public class Main { public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
long n=sc.nextLong();
long k=sc.nextLong();
if(k == 0){
System.out.println(n*n);
return ;
}

        long count = 0; //记录找到的整数对个数
        long temp;
//思路：固定y，找x
        for (long y = k + 1; y <= n; y++) { // x/y>=k,说明y>k
            // 假设n = a*y +b；在每个长度为y的区间里只有（y-k）个数模y余数>=k。
count += n/y*(y-k);
            temp = n%y;
            if(temp >= k) { //再考虑余数b是否>=k
                count += temp-k+1;
            }
        }
System.out.println(count);
}
}

发表于 2018-06-01 16:13:07 回复(3)

WuLiuQi

package test;
import java.util.*;
//循环嵌套是绝对的超时啦！！
public class Test{
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        long n = scanner.nextLong();
        long k = scanner.nextLong();
        int count = 0;
if(k==0){
System.out.print(n*n);
}
        for (long y = k+1; y <= n; y++) {
            /*把所有x可以分成若干区间，区间长度等于y值得大小，利用遍历y值来寻找符合要求能使得余数大于k的 x的个数
例如：用例中n=5，k=2 那么先确定y值可以取 3/4/5

首先先看y=3时：

把所有符合题目范围但是不一定全部符合题目要求的x值罗列出来并分组： 1,2,3 | 4,5

可知所有x值除以y值所得的余数应为（上下对应） 1 2 0 | 1 2
可以看出在一个区间内的余数是有规律的只是在范围内的x不一定刚好就是y的整数倍，也就是划分的区间不一定刚好
全部是完整的，那么可以分为两部分来计算把完整区间的符合余数要求的x加起来，再把不是完整区间的符合余数要求的x加上来就是所需总数*/
count += (n/y)/*区间数*/*(y-k);//余数大于等于k但是余数一定是小于除数的；
//下面就是把不是完整区间的的加上，如果n除以y的余数小于k 那么最后一个区间一定没有符合要求的x 因为n值是最大的余数还小
//于k,不过如果n除以y的余数大于等于k啦那么一定在最后一个区间内还有符合要求的x，
//而此时符合要求的个数就是n%y-（k-1）如果余数要求是大于k不是大于等于这里就是-k
if(n%y>=k)
count+=n%y-(k-1);
        }
        System.out.println(count);
    }
}

发表于 2018-08-10 16:34:58 回复(1)

Rnanprince

package niukeshuati;
import java.util.Scanner;
public class DoubleNumber {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long n = sc.nextLong();
        long k = sc.nextLong();
        if (k == 0) {
            System.out.println(n * n);
            return;
        }

        long count = 0;
        for (long y = k + 1; y <= n; y++) {
            long m = n / y; // x=0+b,x=1y+b,x=2y+b,...,x=(n/y)y+b
            count += m * (y - k);
            // 再考虑余数b是否>=k,即最后一个区间是否有解
            long temp = n % y;
            if (temp >= k) {
                count += n % y - k + 1;
            }

        }
        System.out.println(count);
    }

}

发表于 2018-07-07 15:47:05 回复(1)

博学de叫兽

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        final long n = sc.nextInt();
        final long k = sc.nextInt();
        if (k == 0) {
            System.out.println(n * n);
            return;
        }
        long result = 0;
        for (long y = k + 1; y <= n; y++) {
            long count = n / y;
            result += (y - k) * count + ((n % y) >= k ? n - count * y - k + 1 : 0);
        }
        System.out.println(result);
    }
}

思路：将区间[1, n]切分为[1,y,2y...iy,n]，其中i=n/y。可知在前面i段中，每段有y-k个值满足x的要求。最后一段区间[iy, n]做特殊处理即可。最后，将y做循环，就能找出所有满足要求的数对量啦。

编辑于 2018-09-09 15:08:20 回复(0)

Python

Rider丶

import sys

	n, k = [int(s) for s in sys.stdin.readline().strip().split()]



	# 商最大值h
h = int((n-k)/(k+1))
cnt = 0



	if k==0:
    print(n**2)
else:
    for i in range(h+1):
        y = k+1
        while(y*i+k<=n and y<=n):
            cnt += min(n+1, (i+1)*y)-(y*i+k)
            y += 1
    print(cnt)

# 自己琢磨的比较笨的方法

编辑于 2018-06-25 22:16:15 回复(0)

肥宅大哭.jpg

 
import java.util.*;  public class Main {  public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);  int n = sc.nextInt(),k = sc.nextInt();  int count = 0,count1 = 0;  if (k == 0)
            count = n * n;  else {  for (int i = k + 1;i <= n;i++){
                count += (n / i) * (i - k);  if (n % i >= k)
                    count += n % i - k + 1;    }
        }
        System.out.println(count);    }
}

编辑于 2018-06-13 17:25:50 回复(0)

这世界很cool

//我想说的是一点不难，就是多刷题，这就是运数学规律，做出来的。

public static void main(String[] args) {

       /**
       * 数对问题，给定x，y小于n，且x除以y的余数大于等于k，
       * 给定n，k，求可能出现的数对的个数
       * 整理一下思路：
       * 才用两次for循环，时间复杂度太大
       * 首先，余数最大为k，被除数肯定得大于等于k，余数才能出现k，
       * 本题的小技巧就是，一组数除以一个数是有循环条件出现的，这也就是高中学的循环现象，只需分析完整就好
       * 例如题目给定的 5,2
       * （1,2,3,4,5）/3，循环两次，但是只有一次是完整的，4,5两个数是不完整的循环，
       * 所有4,5需要单独计算，/4,/5类似类推，就可以
       * 下面就是代码分析
       */
       Scanner can = new Scanner(System.in);
       Long n = can.nextLong();
       Long k = can.nextLong();
       long count =0;
       if(k==0){
           System.out.println(n*n);
           return;
       }
       for(Long i = k+1;i<=n;i++){
           //n/i为循环次数，i-k为余数大于k的个数
           count += (n/i)*(i-k);
           //分析不完整的循环，也就是循环剩下的数字
           if(n%i>=k){
               count+=(n%i)-(k-1);
           }
       }
       System.out.println(count);
   }

发表于 2018-07-26 10:07:32 回复(0)

Java

昵称已被占用、

思路：
x % y = k+，则x = y z + k+，遍历y计算x的可能情况。
保证y > k，除数大于余数。
对于每一个特定的y，
xMin = y factor + k
xMax = Math.min(y * (factor + 1) - 1, n)
其差值即为当前y下x的取值，累加即可。

注意：
1.参数的取值，本题xy均为正数，k>=0，故存在x等于0的情况，去除之。
2.除数大于余数，y从k+1开始。
3.累加值小于答案时，考虑是否累积了负值。

import java.util.Scanner;

public class NumberPair {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int k = in.nextInt();

        long count = 0; 
        for (int y = k + 1; y <= n; y++) {
            int factor = 0;
            while (true) {
                int xMin = y * factor + k;
                xMin = xMin == 0 ? 1 : xMin;
                if (xMin > n) {
                    break;
                }
                int xMax = Math.min(y * (factor + 1) - 1, n);
                count += xMax - xMin + 1;
                factor++;
            }
        }
        System.out.println(count);
        in.close();
    }
}

发表于 2018-07-10 10:57:27 回复(0)

梧栖。

def solution(n,k)->int:
    if k==0:
        return (n**2)
    else:
        flag=0
        for y in range(k+1,n+1):
            arry=n//y # 分组共有n//y组
            # 固定y,求满足要求的x个数
            # 计算对每组y有多少x满足要求
            # 根据第一组，y>x>=k时满足，共y-k个
            flag+=arry*(y-k)
            if n%y!=0:
                tmp=n-y*arry # 计算有多少个剩余
                tmp1=tmp-k+1 # 计算剩余中有多少满足x要求
                if tmp1>0:
                    flag+=tmp1
        return flag
n,k = map(int,input().split())
num = solution(n,k)
print(num)

发表于 2020-10-28 19:49:40 回复(0)

dzl

package remain;

import java.util.Scanner;

public class XandY {

    public static void main(String[] args) {
        System.out.println("请输入一个正整数n:");
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        System.out.println("请输入一个非负整数k:");
        int k=sc.nextInt();
        int count=0;

        for(int remain=k;remain<n;remain++) {
            for(int y=remain+1;y<=n;y++) {
                for(int x=1;x<=n;x++) {
                    if(x%y==remain)
                        count++;
                }
            }
        }

        System.out.println(count);

    }
}

发表于 2018-08-28 10:48:09 回复(0)

Java

我想帮你找工作

为什么两个for循环不行呢？

发表于 2018-07-31 17:11:43 回复(1)

XH！

package com.jerehao.playground; import java.util.Scanner; public class No2 { private static int n; private static int k; private static long res = 0; public static void main(String[] args){ int loop = 1;
        System.setIn(No2.class.getResourceAsStream("2.txt"));
        Scanner scanner = new Scanner(System.in); //loop = scanner.nextInt();  for (int i = 0; i < loop; ++i) { n = scanner.nextInt(); k = scanner.nextInt(); solve(); output();
        }
        scanner.close();
    } private static void solve() { if(k == 0) { res = n * (long)(n); return;
        } int t, b; for(b = k + 1; b <= n; ++b) {
            t = (n - k) / b; res += t * (b - k) + Math.min(n, t * b + b - 1) - (t * b + k) + 1;
        }
    } private static void output() {
        System.out.println(res);
    }
}

发表于 2018-07-04 21:07:02 回复(0)

最美的期待_

直接两个for循环不行么

发表于 2018-07-04 12:19:47 回复(0)

JavaScript

是函数不是方法

while(line=readline()){
    var lines = line.split(' ');
    var n = parseInt(lines[0]);
    var k = parseInt(lines[1]);
    var count = 0;
    if(k === 0) print(n*n);
    else{
        for(var y=k+1; y<=n; y++){
            count += Math.floor((n/y))*(y-k) + (n%y>=k?n%y-k+1:0)
        }
        print(count);
    }
}

发表于 2018-06-21 16:42:34 回复(0)