网易在线编程题--数对

曾经终败给现在 2021-09-15 02:52 370阅读 0赞

牛牛以前在老师那里得到了一个正整数数对(x, y), 牛牛忘记他们具体是多少了。

但是牛牛记得老师告诉过他x和y均不大于n, 并且x除以y的余数大于等于k。

牛牛希望你能帮他计算一共有多少个可能的数对。

##### 输入描述: #####

输入包括两个正整数n,k(1 <= n <= 10^5, 0 <= k <= n - 1)。

##### 输出描述: #####

对于每个测试用例, 输出一个正整数表示可能的数对数量。

##### 输入例子1: #####

5 2

##### 输出例子1: #####

##### 例子说明1: #####

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

**常规思路是暴力求解直接遍历，但是时间复杂度0(n\*n)：**

import java.util.Scanner;
    
    public class WangYi_5 {
    	public static void main(String[] args){
    		Scanner input=new Scanner(System.in);
    		int n=input.nextInt();
    		int k=input.nextInt();
    		int count=0;
    		for(int i=1;i<=n;i++){
    			for(int j=1;j<=n;j++){
    				if(i%j>=k){
    					count++;
    				}
    			}
    		}
    		System.out.println(count);
    	}
    }

**另一种思路的复杂度为O(n)：**

> 对于一个b，n范围内的数模b的序列应该是：

> > 0,1,2，......,b-1，0,1,2，......,b-1,........,0,1,2，......,n%b
> 
> 对于前面部分是个循环，其可以通过 (n/b)\*max(0,b-k) 计算
> 
> 对于最后部分是： max(0,n%b-k+1)
> 
> 于是枚举合法的b计算就可以了。
> 
> k=0的情况特殊处理。

> 举个例子：

> > n=10,k=2
> > 
> > 第一步：由于x,y可取1,2,3,4,5,6,7,8,9,10；故1,2,3,4,5,6,7,8,9,10分别对1进行求模运算，得到
> > 
> >   
> >

> > > 0 0 0 0 0 0 0 0 0 0
> > > 
> > >   
> > >

> > 第二步：1,2,3,4,5,6,7,8,9,10分别对2进行求模运算，得到
> > 
> >   
> >

> > > 1 0 1 0 1 0 1 0 1 0
> > 
> >   
> >

> > 第三步：1,2,3,4,5,6,7,8,9,10分别对3进行求模运算，得到
> > 
> >   
> >

> > > 1 2 0 1 2 0 1 2 0 1

> > 第四步：1,2,3,4,5,6,7,8,9,10分别对4进行求模运算，得到  
> > 
> > 
> >   
> >

> > > 1 2 3 0 1 2 3 0 1 2
> > > 
> > >   
> > > 
> > 
> > 第五步：1,2,3,4,5,6,7,8,9,10分别对5进行求模运算，得到
> > 
> >   
> > 
> > 
> > > 1 2 3 4 0 1 2 3 4 0
> > 
> > .   
> >  .   
> > 
> > 
> > .
> > 
> > 第十步：1,2,3,4,5,6,7,8,9,10分别对10进行求模运算，得到

> > > 1 2 3 4 5 6 7 8 9 0

> >   
> > 
> > 
> > **从以上就可以发现规律：**

> > > 比如对于第四步而言，1 2 3 0 1 2 3 0 1 2，可以看出1230，连续两次出现故可用n/b（10/4）来求，
> > > 
> > > 要求1230中比2大的数，可b-k来求，故两个连续的1230中比2大的数就是 (n/b)\*(b-k) ，也即是：(10/4)\*(4-2)=4.
> > > 
> > > 又由于除了两个连续的1230外，还剩下12，要算出剩下的数中大于等于2的个数，
> > > 
> > > 只需算出最后一个数的余数n%b （10%4），其减去k(k=2)加1即可。
> > > 
> > > 也即是： n%b-k+1 ,(10%4-2+1)=1
> > > 
> > >   
> > > 
> 
> **实现代码如下：**

> >     import java.util.Scanner;
> >     
> >     public class WangYi_5 {
> >     	public static void main(String[] args){
> >     		Scanner input=new Scanner(System.in);
> >     		int n=input.nextInt();
> >     		int k=input.nextInt();
> >     		int count=0;
> >     		if(k==0){
> >     			System.out.println(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);
> >     	}
> >     }
> > 
> >   
> > 
> > 
> >   
> >