蓝桥杯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 。
【思路解析 】
在暴力尝试中总结答案的规律文章来源:https://www.toymoban.com/news/detail-733291.html
【代码实现】文章来源地址https://www.toymoban.com/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){
// 这个方法可行,但是时间复杂度为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);
}
}
到了这里,关于蓝桥杯2023年第十四届省赛真题-平方差--题解的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!