tzu220342232

用户名：dotcpp0644624

访问量：169

签　名：

等　　级
排　　名	1324
经　　验	2975
参赛次数	2
文章发表	9
年　　龄	0
在职情况	学生
学　　校	泰州学院
专　　业

　　自我简介：

TA的其他文章

思路很简单，代码很友好（注释），也很短
浏览：22

题解 3142: 蓝桥杯2023年第十四届省赛真题-平方差（数学证明正解+打表找规律）
浏览：4

C++STL 十进制转任意进制
浏览：2

你可能喜欢

C语言程序设计教程（第三版）课后习题11.5 （C++代码）

C语言训练-求s=a+aa+aaa+aaaa+aa...a的值（C语言代码）如果a<0，那就不是这个代码了，哈哈哈哈

题解 3142: 蓝桥杯2023年第十四届省赛真题-平方差（数学证明正解+打表找规律）

　　作者: tzu220342232　　　　发表时间：2024-11-11 23:29:50 浏览：4　|　评论：0　

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

### 数学证明：
对于偶数和奇数分别有如下证明：
	
	对任意偶数可以表示为：2*k，其中k为正整数。假如该偶数满足题目条件：x = y^2-z^2，即2*k = (y + z) * (y - z)则有：y + z = 2, y - z = k，解得：y = k / 2 + 1, z = 1 - k / 2;又因为y、z、为整数，所以 k / 2为整数，则k为2的倍数,则2*k为4的倍数。综上，偶数中只有4的倍数满足条件。
	对于任意奇数可以表示为:2k-1 = (2k-1)*1 = [k + (k - 1)] * [k - (k - 1)] = k2 - (k-1)2（k为正整数）满足条件。
	综上，只有[L, R]中所有奇数和4的倍数满足条件。
### 解题思路:
有了上述结论，现在的任务为：

求区间[L, R]中所有奇数的个数 + 4的倍数的给个数。我们可以采用前缀和思想，先求[1, R]，再求[1, L-1]，然后前后相减即可。
	[1, R]中4的倍数为：R/4，奇数的个数为：(R - 1）/ 2，同理可以求得[1, L-1]，然后相减即为答案。
### 细节注意：
	对于a，b两个整数，a/b上取整为：(a + b - 1) / b；
### 其他方法
	可以先暴力求[1, 100]之间满足条件的值，观察规律，即“打表”，会发现有1，3， 5， 7，9，11， 13， 15， 17，19，21.....（即1~100)之间所有奇数，然后过滤掉奇数后，发现剩余的数的规律为：4，8，12，16，20，24，28，32.....（都为4的倍数），代码入下：
### 时间复杂度：
	O(1)
### 参考代码（正解）:
    #include <bits/stdc++.h>
    
    using namespace std;
    
    void solve() {
    	int L, R;
    	cin >> L >> R;
    
    	long long res = R / 4 - (L - 1) / 4 + (R + 1) / 2 + L / 2;
    	cout << res << '\n';
    }
    
    int main() {
    	ios::sync_with_stdio(false);
    	cin.tie(0);	
		
    	int T = 1;
    	// cin >> T;
    	while (T --) {
    		solve();
    	}
		
    	return 0;
    }
###参考代码（打表找规律）
    #include <bits/stdc++.h>
    
    using namespace std;
    int st[100];
    void show() {
    
    	for (int i = 1; i <= 100; i ++ ) {
    		for (int j = 0; j <= 100; j ++ ) {
    			for (int k = 0; k <= 100; k ++) {
    				if ((j * j - k * k) == i) {
    					if (i % 2) continue;
    					if (!st[i]) {
    						cout << i << '\n';
    					}
    					st[i] = true;
    				}
    			}
    		}
    	}
    }
    
    void solve() {
    	show();
    	int L, R;
    	// cin >> L >> R;
    
    	// long long res = R / 4 - (L - 1) / 4 + (R + 1) / 2 + L / 2;
    	// cout << res << '\n';
    }
    
    int main() {
    	ios::sync_with_stdio(false);
    	cin.tie(0);	
    
    	int T = 1;
    	// cin >> T;
    	while (T --) {
    		solve();
    	}
    
    	return 0;
    }

0.0分

1 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

tzu220342232

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题11.5 （C++代码）

C二级辅导-等差数列（C语言代码）

简单编码（C++代码）（这里推荐用switch）

C语言训练-求s=a+aa+aaa+aaaa+aa...a的值（C语言代码）如果a<0，那就不是这个代码了，哈哈哈哈

C语言训练-求矩阵的两对角线上的元素之和（C语言代码）

题解 3142: 蓝桥杯2023年第十四届省赛真题-平方差（数学证明正解+打表找规律）

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

川哥的吩咐（C语言代码）

C语言程序设计教程（第三版）课后习题8.6 （C语言代码）

数组输出（C语言代码）

大神老白（C语言代码）

Pascal三角（C语言代码）

兰顿蚂蚁（C++代码）

C语言程序设计教程（第三版）课后习题7.2 （C语言代码）

回文数字（C语言代码）

C二级辅导-公约公倍（C语言代码）

tzu220342232

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题11.5 （C++代码）

C二级辅导-等差数列 （C语言代码）

简单编码 （C++代码）（这里推荐用switch）

C语言训练-求s=a+aa+aaa+aaaa+aa...a的值 （C语言代码） 如果a<0，那就不是这个代码了，哈哈哈哈

C语言训练-求矩阵的两对角线上的元素之和 （C语言代码）

题解 3142: 蓝桥杯2023年第十四届省赛真题-平方差（数学证明正解+打表找规律）

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

川哥的吩咐 （C语言代码）

C语言程序设计教程（第三版）课后习题8.6 （C语言代码）

数组输出 （C语言代码）

大神老白 （C语言代码）

Pascal三角 （C语言代码）

兰顿蚂蚁 （C++代码）

C语言程序设计教程（第三版）课后习题7.2 （C语言代码）

回文数字 （C语言代码）

C二级辅导-公约公倍 （C语言代码）

C二级辅导-等差数列（C语言代码）

简单编码（C++代码）（这里推荐用switch）

C语言训练-求s=a+aa+aaa+aaaa+aa...a的值（C语言代码）如果a<0，那就不是这个代码了，哈哈哈哈

C语言训练-求矩阵的两对角线上的元素之和（C语言代码）

　　评论区

川哥的吩咐（C语言代码）

数组输出（C语言代码）

大神老白（C语言代码）

Pascal三角（C语言代码）

兰顿蚂蚁（C++代码）

回文数字（C语言代码）

C二级辅导-公约公倍（C语言代码）