我要招人

去企业版

首页 > 试题广场 >

数对

[编程题]数对

热度指数：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

输出

说明

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

算法知识视频讲解

Java

牛客220397715号

优化题太磨人了，我晕了TAT

import java.util.*;

public class Main{
    public static void main(String[] args){
        //收数据
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int k = sc.nextInt();
        long possibleAmount = 0;//因为取值量达到10^10之广，已经溢出了int的表数范围
        //需要优化。省略不必要步骤。
        //分析得知可以不用循环判别法得出结果。在x>y的部分，只有一部分取值满足条件。
        //只有在ny+k<=x<(n+1)y的范围内，才是符合条件的，需要根据这点化简
        possibleAmount += (long)(n-k)*(n-k+1)/2;//y>x部分，全部满足
        //注意，因为要返回long类型，两个int计算结果是int，溢出以后就变为负值，有long参与，结果就为long
        //y=x肯定不满足因此忽略，接下来判断y<x部分
        //因为x属于[k,n]，y属于[k+1,n]，接下来的判断域为y属于[k+1,n-1]，x属于[y+1,n]
        int xTop = 0;
        int xBottom = 0;
        for(int y = k+1; y<n ;y++) {//y属于[k+1,n-1]
        	for(int i = 1; (y*i+k)<=n; i++) {//x属于[y+1,n]
        		xTop = ((i+1)*y)>(n+1) ? n+1 : (i+1)*y;
        		xBottom = (y*i+k)<(y+1) ? y+1 : y*i+k;
        		possibleAmount += xTop-xBottom;
        	}
        }
        System.out.println(possibleAmount);
        sc.close();
    }
}

发表于 2020-03-09 22:34:45 回复(1)

Java

1+½+¼+⅛+...

import java.util.Scanner;

public class Main{
    public static void main(String[] args){
        Scanner input = new Scanner(System.in);
        int n = input.nextInt();
        int k = input.nextInt();
        System.out.println(Solution(n, k));
    }
    public static long Solution(int n, int k){
        long sum = 0L;
        if(k != 0){
            for(int y = k + 1; y <= n; y ++){
            sum += n/y * (y - k) + ((n%y < k) ? 0 : (n%y - k + 1) );           
        }
        }
        if(k == 0)
            sum = (long)n * n;
        return sum;
    }
}

编辑于 2019-09-04 14:00:25 回复(0)

Java

啊啊啊，求offer

import java.util.Scanner;

public class Main{
    public static void main(String [] args)
    {
        Scanner sc = new Scanner(System.in);
        long n = sc.nextInt();    //获取到n
        long k = sc.nextInt();    //获取懂啊到k
      // System.out.println("n:" + n + "k:" + k);
        //想不明白了
        //我这里把数据分成了两个部分
        //1，X <= Y的时候， x自己就是余数，所以直接计算就是了
        //是有规律的，因为余数就是x, 所以，值是1+2+3+... + n-k
        //求和公式得到, (n-k)*(n-k+1)/2,
        //int sum = (n-k)*(n-k+1)/2;
        long sum = (n-k)*(n-k+1)/2;


        //2.x<y的时候，就会出现多

        //那就换思路，就是把y作为基点，反过来看比y大的数有多少
        for(long y=k+1; y<=n; y++)
        {
            long div = n/y;    //得到除数
            long rem = n%y;    //得到余数

            if(div >= 1)    //y一定比x大
            {
                sum = sum + (div-1)*(y-k);        //这是处理整除部分的数据

            }


            if(rem >= k)        //处理余数部分，但是要注意，如果k等于0，要小心，把余数为0的重复计算
            {
                sum = k != 0? (sum + rem-k+1): (sum + rem-k);
            }


        }
        System.out.println(sum);
        return;
    }
}

发表于 2019-08-26 00:38:54 回复(0)

Java

咽喉上的刀

JAVA解答：首先感谢大佬的解题思路。数学还是很重要啊2333333

import java.util.Scanner;

public class Main {
    public static void main(String[] args){
        Scanner input = new Scanner(System.in);
        long n = input.nextInt();
        long k = input.nextInt();
        long count = 0;
        if (k==0)
            System.out.println(n*n);
        else {
            for (long i = k+1;i<=n;i++){
                //+号前是分成一个一个小间隔，将每个小间隔里满足条件的个数乘以小间隔个数。
                //+号后求的是最后一个小间隔里面是否有满足条件的。
                count += (n/i)*(i-k) + Math.max(0,n%i-k+1);
            }
            System.out.println(count);
        }
    }
}

编辑于 2019-08-04 21:51:15 回复(0)

Java

蛋哥归来

一定要用long而不是int

发表于 2018-04-04 11:24:21 回复(1)

Java

懷戀，那弎年

import java.util.*;

public class Main{
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long n = sc.nextInt();
        long k = sc.nextInt();
        long ans = 0L;
        if (k == 0) {
            ans = n * n; // 任何两对数的余数都是大于等于零
        } else {
            for (long y = k + 1; y <= n; y++) {
                ans += (n / y) * (y - k) + Math.max(0, n % y - k + 1);
                // 假设n=10,k=3，则对y来说只能是4,5,6,7,8,9,10
                // 当y=4,(n/y)*(y-k)代表x小于等于8(8是4的整数倍)时有(3,4),(7,4)，Math.max(0,n%y-k+1)代表x大于8时符合题意的对数为0
                // 当y=5,(n/y)*(y-k)代表x小于等于10(10是5的整数倍)时有(3,5),(4,5),(8,5),(9,5)，Math.max(0,n%y-k+1)代表x大于10时符合题意的对数为0
                // 当y=6,(n/y)*(y-k)代表x小于等于6时有(3,6),(4,6),(5,6),Math.max(0,n%y-k+1)代表x大于6时符合题意的对数为2,分别是(9,6),(10,6)
                // 当y=7,(n/y)*(y-k)代表x小于等于7时有(3,7),(4,7),(5,7),(6,7),Math.max(0,n%y-k+1)代表x大于7时符合题意的对数为1,是(10,7)
                // ...以此类推
            }
        }
        System.out.println(ans);
    }
}

发表于 2018-03-28 18:34:12 回复(5)

Java

山柴贩

// 时间复杂度O(N)
// 将除数y从k+1 开始计算，除数为y时，数对的个数包括两部分： n/y*(y-k) 和多出来的另一部分，这部分需要看
// n%y 和k的大小关系 
import java.util.*;
public class Main{
    public static void main(String[] arsg){
        Scanner sc= new Scanner(System.in);
        int n = sc.nextInt();
        int k = sc.nextInt();
        long sum = 0;
        int t = 0;
        int tt = 0;
        for(int i=k+1;i<=n;i++){
            t++;
            tt = (n%i - k + 1) >0 ? (n%i - k + 1):0;
            sum+=n/i*t+tt;
        }
        if(k == 0) sum-=n;// k=0 特殊情况  多计算了n次
        System.out.print(sum);
    }
}

发表于 2018-03-28 15:55:45 回复(8)

提交观点

问题信息

C++工程师 golang工程师 iOS工程师安卓工程师运维工程师前端工程师算法工程师测试工程师 PHP工程师网易 2019 基础数学数学 Java工程师

来自：网易2019实习生招聘...

上传者：小小

难度：

7条回答 358收藏 26876浏览

通过挑战的用户

查看代码

Jtyyds

2023-03-06 13:12:57
周周喵

2022-09-16 11:59:30
游辞

2022-09-15 09:58:15
牛客18908...

2022-09-14 19:11:05
韵秋梧桐

2022-09-14 15:04:32

数对

输入描述:

输出描述:

输入

输出

说明

问题信息

热门推荐

通过挑战的用户

相关试题