#创人计划# A+B 神秘恩方做法

userId_undefined

复仇者_帅童

CSP-J一等奖出题人

2025-08-27 14:33:47

发布于：广东

65阅读
0回复
0点赞

注意到 a+b=(a+b)2=a2+2ab+b2a+b=\sqrt{(a+b)^2}=\sqrt{a^2+2ab+b^2}。

我们使用累加方法求出 a2,2ab,b2a^2,2ab,b^2，然后再将他它们一个一个加起来，注意到这个式子一定是整数，通过试根号来得出。

如何试根号：
将 ii 从 11 枚举到 ∞\infty，判断 i2i^2 是否等于 a2+2ab+b2a^2+2ab+b^2 即可。
但是如果这样配上累加算乘法的话太慢了，时间复杂度是 O(n3)O(n^3) 的，需要优化。
注意到 i2=(i−1)2+2×i−1i^2= (i-1)^2+2\times i-1。所以我们可以递推 O(n2)O(n^2) 求出。
这样就可以以 O(n2)O(n^2) 的复杂度完美地解决这个问题了。

在具体实现时记得开 long long。

附上代码：

#include <iostream>
#include <cstdio>
#define int long long
using namespace std;
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	int n, m;
	cin >> n >> m;
	int ans = 0;
	for(int i = 1; i <= n; i++) for(int j = 1; j <= n; j++) ans++;
	for(int i = 1; i <= n; i++) for(int j = 1; j <= m; j++) ans++;
	for(int i = 1; i <= n; i++) for(int j = 1; j <= m; j++) ans++;
	for(int i = 1; i <= m; i++) for(int j = 1; j <= m; j++) ans++;
	int cur = 0;
	for(int i = 1;; i++){
		for(int j = 1; j <= i; j++) cur++;
		for(int j = 1; j <= i; j++) cur++;
		cur--;
		if(cur == ans){
			cout << i;
			return 0;
		}
	}

	return 0;
}

该代码在递推计算 i2i^2 时使用了滚动数组的方法，大家可以学习一下。

userId_undefined
去预览
0/2000

全部评论 12

热门讨论