鍍金池/ 問答/Java  Python  C  C++/ 編程題代碼解釋

編程題代碼解釋

正整數對(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的區(qū)間里只有(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這兩句結合為什么就能夠求出最終個數?

回答
編輯回答
尋仙

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

2017年2月12日 04:19
編輯回答
柒槿年

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

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

假設n = a*y +b;在每個長度為y的區(qū)間里只有(y-k)個數模y余數>=k

count += temp-k+1;是計算n = a*y +b中的b里面還有多少個滿足條件的數對。

舉個例子,n=18,k=3。

首先,y肯定是大于3的,因為3以內的除數余數不可能大于等于3。所以for循環(huán)是從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這兩個數。

建議你在數軸上畫一下,應該就能明白了。

2018年2月10日 09:04