2018年春招网易笔试题-数对问题o(n-k)解法

桃扇骨 2022-05-28 02:41 160阅读 0赞

# 题目描述 #

牛牛以前在老师那里得到过一个整数对（x,y），牛牛忘记他们具体是多少了，只记得老师说过，x和y均不大于n，且x%y不小于k，牛牛希望你能帮他计算一共有多少种可能的整数对。

输入描述：两个整数n，k。其中1<=n<=10^5, 0<=k<=n-1

输出描述：输出可能的正整数对的个数。

# 思路： #

暴力破解所有整数对，需要o(n^2)，会超时。

其实是个数学问题：

1. y必然大于k，x必然不小于k，才可能产生不小于k的余数；

2.x一定可以表示为：x = i\*y + k' (0<x<= n) ,其中i可以理解为倍数,（0<= i < n/y，共n/y个可能的i），k'为（k,y-1）之间的任意数，共（y-k）种；所以一共有（n/y）\*（y-k）种情况。

3.当i取到n/y时，x = i\*y + k'可能大于n，所以要计算这里面可能出现的，不大于n的情况，即max(0, n- ( i\*y+ k) ));

针对以上三个问题，可以大大简化计算的复杂度。

# 代码： #

import java.util.*;
    public class Main {
        public static void main(String args[]) {
            Scanner scanner = new Scanner(System.in);
            int n = scanner.nextInt();
            int k = scanner.nextInt();
            int y = 1;
            int factor = 1;
            long sumCnt = 0;
            if(k == 0) {
                System.out.println(n*n);
            }
            for(y = k + 1; y <= n; y++) {
                factor = n / y;
                sumCnt += factor * (y - k);
                sumCnt +=  Math.max(0, n - (factor * y + k) + 1);
            }
            System.out.println(sumCnt);
        }
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，160人围观）

还没有评论，来说两句吧...

相关阅读

相关 java笔试题0_联想2018秋招Java笔试题

在牛客网看了这么多题，也学到了很多，分享一下我做过的联想试题，希望对大家有所帮助。单选题 1.在数据结构中，从逻辑上可以把数据结构分为() A.动态结构和静态结构 B

忘是亡心i/ 2022年10月22日 14:54/ 0 赞/ 223 阅读

相关 2017年网易测试开发实习生笔试题

15道单选，5道多选，3道编程，1道问答（\有些选择题我没记选项。。。有些题是没记下来，反正大家看看，知道考点是什么就好啦） 1.16位又符合整型的数据范围是？

不念不忘少年蓝@/ 2022年10月01日 02:51/ 0 赞/ 176 阅读

相关 2017春招笔试题

2017年3月春招以来，陆续参加了不少公司的技术在线笔试，题型各异，有的题目现在还没解决，现将能回忆起的记录一下。一、空间有15个点，构成立体多面体，最多20个面，问

Dear 丶/ 2022年06月15日 10:45/ 0 赞/ 243 阅读

相关 2018网易笔试题-操作序列

编程题\] 操作序列时间限制：2秒空间限制：32768K 小易有一个长度为n的整数序列,a\_1,...,a\_n。然后考虑在一个空序列b上进行n次以下操作: 1

川长思鸟来/ 2022年06月09日 11:17/ 0 赞/ 233 阅读

相关网易2018春招笔试编程题——nk数对

题目描述：牛牛以前在老师那里得到了一个正整数数对(x, y), 牛牛忘记他们具体是多少了。但是牛牛记得老师告诉过他x和y均不大于n, 并且x除以y的余数大于等于k。

￡神魔★判官ぃ/ 2022年05月28日 06:20/ 0 赞/ 242 阅读

相关 18网易春招笔试题-牛牛的背包-记忆化搜索

/\ 牛牛准备参加学校组织的春游, 出发前牛牛准备往背包里装入一些零食, 牛牛的背包容量为w。牛牛家里一共有n袋零食, 第i袋零食体积为v\[i\]。

我就是我/ 2022年05月28日 03:14/ 0 赞/ 146 阅读

相关 2018年春招网易笔试题-数对问题o(n-k)解法

题目描述牛牛以前在老师那里得到过一个整数对（x,y），牛牛忘记他们具体是多少了，只记得老师说过，x和y均不大于n，且x%y不小于k，牛牛希望你能帮他计算一共有多少种可能

桃扇骨/ 2022年05月28日 02:41/ 0 赞/ 161 阅读

相关网易笔试题-堆棋子

转自：[https://blog.csdn.net/u013616945/article/details/77750698][https_blog.csdn.net_u0136

小咪咪/ 2022年05月21日 01:19/ 0 赞/ 206 阅读

相关字节跳动2018年校招笔试题

1 ![0069McTXly1g1zwedsiuaj30h20cewfi.jpg][] 思路 DFS 找出最大连通分量代码 mat = []

╰+哭是因爲堅強的太久メ/ 2022年02月20日 07:38/ 0 赞/ 328 阅读

相关网易游戏2020研发笔试题

（1）大概是对一个序列中统计每个数的二进制的位数1个数，并对其按1的个数归类，输出总共有几类 include<iostream> include<set>

悠悠/ 2021年11月01日 04:50/ 0 赞/ 289 阅读