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

桃扇骨 2022-05-28 02:41 151阅读 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);
        }
    }

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

发表评论取消回复

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

相关阅读