蓝桥杯2023年第十四届省赛真题-平方差

时间限制: 3s 内存限制: 320MB 提交: 2379 解决: 469

题目描述

给定 L, R，问 L ≤ x ≤ R 中有多少个数 x 满足存在整数 y,z 使得 x = y2 − z2。

输入格式

输入一行包含两个整数 L, R，用一个空格分隔。

输出格式

输出一行包含一个整数满足题目给定条件的 x 的数量。

样例输入

复制

1 5

样例输出

复制

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 。

【思路解析 】

在暴力尝试中总结答案的规律

【代码实现】

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){// 这个方法可行，但是时间复杂度为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发现 x要么为奇数要么为4的倍数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发现 x要么为奇数要么为4的倍数// 得到这个规律后，可以统计这样的数目应当为 F(R) = R / 4 + (R + 1) / 2;假设 L == 1// 所以实际数目应该为F(R) - F(L - 1)return (R / 4 + (R + 1) / 2) - ((L - 1) / 4 + (L) / 2);}
}