题目概述

洛谷6786

解题报告

假设 $(b_i,b_j)=A,b_i=BA,b_j=CA(C>B)$ ，然后推式子：

$$ BA+CA+A={BA\cdot CA\over A}\\ BA+CA+A=ABC\\ B+C+1=BC\\ (B-1)(C-1)=2\\ ∴B=2,C=3 $$

又因为 $(2,3)=1$ ，所以反过来得知 $A$ 可以任取。

那么就是 $b_i=2A,b_j=3A$ 之间可以连边，用并查集合并，求最大的块就好了。

注意合并重复的。

示例程序

#include<map>
#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long LL;
const int maxn=300000;

int n,a[maxn+5],fat[maxn+5];LL sum[maxn+5],ans;map<int,int> lst;

int getfa(int x) {return x==fat[x]?x:fat[x]=getfa(fat[x]);}
void Merge(int x,int y){
    x=getfa(x);y=getfa(y);if (x==y) return;
    fat[x]=y;sum[y]+=sum[x];
}
int main(){
    scanf("%d",&n);for (int i=1;i<=n;i++) scanf("%d",&a[i]);
    sort(a+1,a+1+n);int N=n;n=0;
    for (int i=1,j;i<=N;i=j){
        for (j=i+1;j<=N && a[i]==a[j];j++);
        a[++n]=a[i];fat[n]=n;sum[n]=(LL)(j-i)*a[i];
    }
    for (int i=1;i<=n;i++){
        if (!(a[i]%2)) {if (lst[a[i]/2]) Merge(i,lst[a[i]/2]);lst[a[i]/2]=i;}
        if (!(a[i]%3)) {if (lst[a[i]/3]) Merge(i,lst[a[i]/3]);lst[a[i]/3]=i;}
    }
    for (int i=1;i<=n;i++) if (i==getfa(i) && sum[i]>ans) ans=sum[i];
    printf("%lld\n",ans);return 0;
}