编程题代码解释

正整数对(x,y),x,y都小于等于n,x/y的余数大于等于k,输入为n,k,输出有多少个,比如输入5 2,输出为7, 对数分别为(2,3)(2,4)(2,5)(3,4)(3,5)(4,5)(5,3),代码如下:


import java.util.Scanner;

public class Main {

    public static void main(String[] args) {        
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int k = scanner.nextInt();
        System.out.println(searchCount(n, k));
    }
    public static int searchCount(int n, int k) {
        int count = 0;  //记录找到的整数对个数
        int temp;

        //思路:固定y,找x

        for (int 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;
            }
        }        
        return count;
    }
}

为什么x%y>=k,就能推断出说明y>k?count += n/y*(y-k)和count += temp-k+1这两句结合为什么就能够求出最终个数?

阅读 2.4k
2 个回答

x%y>=k的意思是x除以y的余数大于等于k,余数肯定是小于y的,因此y肯定大于k。

count += n/y*(y-k)的意思就是那句注释:

假设n = a*y +b;在每个长度为y的区间里只有(y-k)个数模y余数>=k

count += temp-k+1;是计算n = a*y +b中的b里面还有多少个满足条件的数对。

举个例子,n=18,k=3。

首先,y肯定是大于3的,因为3以内的除数余数不可能大于等于3。所以for循环是从k+1开始的。

对于任何一个y,例如7,首先把n=18写成18 = 2 * 7 + 4的形式,也就是把1~18这段范围内的整数分成了1~7、8~14、15~18这三段。前两段里面每段都有y-k=4个数满足余数大于等于3的要求。而最后一段里面只有b-k+1=2个数满足,也就是17、18这两个数。

建议你在数轴上画一下,应该就能明白了。

1.X%y结果为X除以Y的余数,余数<=除数,而余数>k,那么y肯定>k
2.count += n/y(y-k) 等价于 count = count + n/y(y-k)
3.和2同理

撰写回答
你尚未登录,登录后可以
  • 和开发者交流问题的细节
  • 关注并接收问题和回答的更新提醒
  • 参与内容的编辑和改进,让解决方法与时俱进
推荐问题