自动搬运

查看原文

来自洛谷，原作者为

	Reanap 你面向名为希望的绝望微笑。

搬运于2025-08-24 22:20:22，当前版本为作者最后更新于2020-04-17 21:31:27，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

这道题还是比较简单，我相信$50\%$以上的参赛选手都能够拿到良心出题人的这$100$pts。（出题人现在才想起交题解）

首先我们观察式子：

$(a_j-b_i) \times (b_j+b_i)=a_j \times b_i + a_i \times b_j$

发现这个式子非常地不好看，我们想要把下标相同放在一块儿（方便预处理维护），所以我们把式子括号拆开，得：

$a_j \times b_j + b_i \times a_j - b_j \times b_i - b_i \times b_i = a_j \times b_i + a_i \times b_j$

移项合并同类项，提取公因式得：

$(a_j - a_i - b_i) \times b_j = b_i \times b_i$

我们设 $k = a_j - a_i - b_i$

则有:

$k \times b_j = b_i \times b_i$

和

$a_j = a_i + b_i + k$

因此我们就列出这样一个不定方程组，只要知道了一个未知项就可以知道其他项。

因此我们考虑枚举$k$，观察式子可知$k$必然是$b_i \times b_i$的因数。而且题目中$b_i$比较小，因此完全可以去枚举，然后去计算$a_i$和$b_i$，之后在判断是否存在$a_i$和$b_i$这种元素的情况（可以使用map来维护，其实$b$的极限数据可以提升到$1000$去卡$\log n$的map，但出题人比较良心）。

如果还有不懂的可以去看看下面的代码：

#include <map>
#include <cstdio>
#include <algorithm>
using namespace std;
const int MAXN = 5e4 + 5;
map <pair<int , int> , int> M;
int n , a[MAXN] , b[MAXN] , ans[MAXN];
signed main() {
//	freopen("11.in" , "r" , stdin);
//	freopen("11.out" , "w" , stdout);
   scanf("%d" , &n);
   for (int i = 1; i <= n; ++i) {
   	scanf("%d %d" , &a[i] , &b[i]);
   }
   for (int i = n; i >= 1; --i) {
   	int res = 1e9;
   	for (int j = 1; j <= b[i]; ++j) {
   		if(b[i] * b[i] % j == 0) {
   			int x = 0 , y = 0;
   			if(M[make_pair(a[i] + b[i] + j  , b[i] * b[i] / j)]) {
   				x = M[make_pair(a[i] + b[i] + j  , b[i] * b[i] / j)];
   			}
   			if(M[make_pair(a[i] + b[i] + b[i] * b[i] / j  , j)]) {
   				y = M[make_pair(a[i] + b[i] + b[i] * b[i] / j  , j)];
   			} 
   			if(x) res = min(res , x);
   			if(y) res = min(res , y);
   		}
   	}
   	if(res != 1e9) ans[i] = res;
   	else ans[i] = -1;
   	M[make_pair(a[i] , b[i])] = i;
   }
   for (int i = 1; i <= n; ++i) printf("%d\n" , ans[i]);
   return 0;
}