藍橋杯2023年第十四屆省賽真題-平方差

時間限制: 3s?內(nèi)存限制: 320MB?提交: 2379 解決: 469

題目描述

給定 L, R，問 L ≤ x ≤ R 中有多少個數(shù) x 滿足存在整數(shù) y,z 使得 x = y2?? z2。

輸入格式

輸入一行包含兩個整數(shù) L, R，用一個空格分隔。

輸出格式

輸出一行包含一個整數(shù)滿足題目給定條件的 x 的數(shù)量。

樣例輸入

復(fù)制

1 5

樣例輸出

復(fù)制

4

提示

1 = 1^2?? 0^2 ；

3 = 2^2 ? 1^2 ；

4 = 2^2 ? 0^2 ；

5 = 3^2 ? 2^2 。

對于 40% 的評測用例，LR ≤ 5000 ；

對于所有評測用例，1 ≤ L ≤ R ≤ 10^9?。

【思路解析 】

在暴力嘗試中總結(jié)答案的規(guī)律

【代碼實現(xiàn)】文章來源地址http://www.zghlxwxcb.cn/news/detail-733291.html

import java.util.Scanner;

/**
 * @ProjectName: study3
 * @FileName: Ex1
 * @author:HWJ
 * @Data: 2023/9/16 22:27
 */
public class Ex1 {
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        int L = input.nextInt();
        int R = input.nextInt();
        //System.out.println(getNums2(L, R));
        System.out.println(getNums3(L, R));
    }

    public static int getNums1(int L, int R){
        // 這個方法可行，但是時間復(fù)雜度為O(N^2)，不滿足題目要求
        int s = (R + 1) / 2;
        int e = (int) Math.sqrt(L) + 1;
        int ans = 0;
        boolean[] have = new boolean[R - L + 1];
        for (int i = s; i >= e; i--) {
            for (int j = i - 1; j >= 0; j--) {
                int a = (i + j) * (i - j);
                if (a >= L && a <= R && !have[a - L]) {
                    ans++;
                    have[a - L] = true;
                } else if (a > R) {
                    break;
                }
            }
        }
        return ans;
    }

    public static int getNums2(int L, int R){
        // 通過觀察所有可行的x發(fā)現(xiàn) x要么為奇數(shù)要么為4的倍數(shù)
        int ans = 0;
        for (int i = L; i <= R; i++) {
            if (i % 4 == 0 || i % 2 != 0){
                ans++;
            }
        }
        return ans;
    }

    public static int getNums3(int L, int R){
        // 通過觀察所有可行的x發(fā)現(xiàn) x要么為奇數(shù)要么為4的倍數(shù)
        // 得到這個規(guī)律后，可以統(tǒng)計這樣的數(shù)目應(yīng)當為 F(R) = R / 4 + (R + 1) / 2;假設(shè) L == 1
        // 所以實際數(shù)目應(yīng)該為F(R) - F(L - 1)

        return (R / 4 + (R + 1) / 2) - ((L - 1) / 4 + (L) / 2);
    }
}

到了這里，關(guān)于藍橋杯2023年第十四屆省賽真題-平方差--題解的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！