题解：P6393 隔离的日子

· · 题解

思路

我们可以先把题目给的式子简化：

\begin{aligned} (a_j - b_i) \times (b_j + b_i) &= a_j \times b_i + a_i \times b_j \\ a_jb_j + a_jb_i - b_ib_j - {b_i}^2 &= a_jb_i + a_ib_j \\ a_jb_j - b_ib_j - {b_i}^2 &= a_ib_j \\ a_jb_j - b_ib_j - a_ib_j &= {b_i}^2 \\ (a_j - b_i - a_i)b_j &= {b_i}^2 \end{aligned}

因为 1 \le b_i \le 100 ，所以我们可以枚举 {b_i}^2 的因子为 a_j - b_i - a_i ，求出 a_j 和 b_j ，然后输出 j > i 的 (a_j, b_j) 的最小 j 即可。枚举的时候可以从后往前枚举，这样就可以边统计答案边统计 (a_j, b_j) 的位置了。

代码

#include<bits/stdc++.h>
#define PII pair<int,int>
#define int long long
using namespace std;
const int MAXN=5e4+5;
int n,a[MAXN],b[MAXN],c[MAXN],mi=1e18;map<PII,int>mp;
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    //freopen(".in","r",stdin);
    //freopen(".out","w",stdout);
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i]>>b[i];
    for(int i=n;i>=1;i--){
        mi=1e18;
        for(int j=1;j*j<=b[i]*b[i];j++)
            if((b[i]*b[i])%j==0){
                int x=b[i]*b[i]/j,y=j;
                int aj=x+a[i]+b[i],bj=j;
                if(mp[{aj,bj}])mi=min(mi,mp[{aj,bj}]);
                aj=y+a[i]+b[i],bj=b[i]*b[i]/y;
                if(mp[{aj,bj}])mi=min(mi,mp[{aj,bj}]);
            }if(mi==1e18)mi=-1;
        mp[{a[i],b[i]}]=i,c[i]=mi;
    }for(int i=1;i<=n;i++)cout<<c[i]<<'\n';
    return 0;
}