【题目链接】

ybt 1404：我家的门牌号
OpenJudge NOI 2.1 7649:我家的门牌号
OpenJudge NOI 小学奥数 7649:我家的门牌号
注意：一本通OJ和OpenJudge上的这道题条件不同，ybt上为“其余各家门牌号”，OpenJudge上为“所有门牌号”，导致列出的方程不同。两题解题思路相似。

【题目考点】

1. 枚举

枚举求方程的解

【解题思路】

ybt 1404：我家的门牌号

设我家门牌号为x，总共有y家
那么所有人家门牌号之和为：$(1+y)y/2$
除了自己家以外所有人家门牌号之和为：$(1+y)y/2-x$
除了自己家以外所有人家门牌号之和，减去自己家门牌号的两倍，结果为n：$(1+y)y/2-x-2x=n$ ，即$(1+y)y/2-3x=n$

枚举写法1：

• 枚举对象：$x、y$
• 枚举范围：$y$的范围为$1\sim 100000$，$x$的范围为$1\sim y$。
• 判断条件：方程$(1+y)y/2-3x=n$

写两层循环分别枚举y和x，判断枚举出的x和y是否满足方程，如果满足则输出解。数据保证有唯一解，所以输出一组解后直接结束程序。
该枚举写法的复杂度为$O(y^2)$。写出代码提交可以通过，不过当y接近100000时，会时间超限。

枚举写法2：

• 枚举对象：$y$
• 枚举范围：$y$的范围为$1\sim 100000$
  根据方程$(1+y)y/2-3x=n$可以推出$x=((1+y)y/2-n)/3$
  x是门牌号，必须是整数，因此如果有解，$(1+y)y/2-n$必须是$3$的倍数。
  而后求出x，由于$x$的范围为$1\sim y$，所以一定满足$1\le x\le y$
  如果当前的x满足这些条件，那么直接输出x、y就是一组解。
  该方法的时间复杂度为$O(y)$，可以通过。

OpenJudge NOI 2.1 7649:我家的门牌号

OpenJudge NOI 小学奥数 7649:我家的门牌号

由于该题条件为所有的门牌号之和减去我家门牌号的两倍，恰好等于n
所以方程为：$(1+y)y/2-2x=n$
其他方面的思路和写法和上面的描述是相同的，不再赘述。

童程OJ 11613 门牌号码必须使用$O(y)$的写法才能通过。

【题解代码】

ybt 1404：我家的门牌号

• 写法1：复杂度$O(y^2)$

#include<bits/stdc++.h>
using namespace std;
int main()
{//设我家门牌号为x，总共有y家，可以列出方程：(1 + y)y/2 - x - 2*x = n 枚举求解
	int n;
	cin >> n;
	for(int y = 1; y <= 100000; ++y)
		for(int x = 1; x <= y; ++x)
			if((1+y)*y/2-3*x == n)
			{
				cout << x << ' ' << y;
				return 0;		
			}
	return 0;
}

• 写法2：复杂度$O(y)$

#include<bits/stdc++.h>
using namespace std;
int main()
{//设我家门牌号为x，总共有y家，可以列出方程：(1 + y)y/2 - 3*x = n 枚举求解
	int n;
	cin >> n;
	for(int y = 1; y <= 100000; ++y)
	{
		if(((1+y)*y/2-n)%3 == 0)
		{
			int x = ((1+y)*y/2-n)/3;
			if(x >= 1 && x <= y)
			{
				cout << x << ' ' << y;
				return 0;
			}
		}
	}
	return 0;
}

OpenJudge NOI 2.1 7649:我家的门牌号

OpenJudge NOI 小学奥数 7649:我家的门牌号

• 写法1：$O(y^2)$

#include<bits/stdc++.h>
using namespace std;
int main()
{//设我家门牌号为x，总共有y家，可以列出方程：(1 + y)y/2 - 2*x = n 枚举求解
	int n;
	cin >> n;
	for(int y = 1; y <= 100000; ++y)
		for(int x = 1; x <= y; ++x)
			if((1+y)*y/2-2*x == n)
			{
				cout << x << ' ' << y;
				return 0;		
			}
	return 0;
}

• 写法2：$O(y)$

#include<bits/stdc++.h>
using namespace std;
int main()
{//设我家门牌号为x，总共有y家，可以列出方程：(1 + y)y/2 - 3*x = n 枚举求解
   int n;
   cin >> n;
   for(int y = 1; y <= 100000; ++y)
   {
		if(((1+y)*y/2-n)%2 == 0)
   		{
   			int x = ((1+y)*y/2-n)/2;
   			if(x >= 1 && x <= y)
   			{
   				cout << x << ' ' << y;
   				return 0;
   			}
   		}
   }
   return 0;
}