用地方别名做网站名,网站建设改版升级,百度平台官网,青岛网站域名备案查询蓝桥杯2023年第十四届省赛真题-平方差
时间限制: 3s 内存限制: 320MB 提交: 2379 解决: 469
题目描述
给定 L, R#xff0c;问 L ≤ x ≤ R 中有多少个数 x 满足存在整数 y,z 使得 x y2 − z2。
输入格式
输入一行包含两个整数 L, R#xff0c;用一个空格分隔。
输出格…蓝桥杯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);}
}
