编程题代码解释

Question

正整数对（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这两句结合为什么就能够求出最终个数？

Answer 1

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这两个数。

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

Answer 2

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