自动搬运

查看原文

来自洛谷，原作者为

	Alex_Wei **

搬运于2025-08-24 22:23:59，当前版本为作者最后更新于2020-08-26 19:32:13，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

因为是简单题所以放一下官方题解吧。

题面传送门。

题意简述：从给定序列 $a$ 中选出一个子序列满足：对于所有不为最大值的 $b_i$，总有 $b_j$ 使得 $b_i+b_j+\gcd(b_i,b_j)=\mathrm{lcm}(b_i,b_j)$。求子序列所有数之和的最大值。

Subtask 1：$n\leq2$。

傻子都会做的部分分。

Subtask 2：$n\leq 17$。

枚举 $a$ 的所有子集并判断是否合法。可以预处理出所有合法对 $(i,j)$ 满足 $a_i+a_j+\gcd(a_i,a_j)=\mathrm{lcm}(a_i,a_j)$。时间复杂度为 $O(2^nn^2)$。如果不预处理时间复杂度为 $O(2^nn^2\log a_i)$，较难通过。

Subtask 4：$n\leq 3\times 10^3$。

枚举所有 $i,j$ 使得 $i<j$ 且 $a_i+a_j+\gcd(a_i,a_j)=\mathrm{lcm}(a_i,a_j)$，将所有这样的 $i,j$ 之间连一条边，最后求出连通块里所有点的权值之和的最大值即可。时间复杂度 $O(n^2\log a_i)$。

Subtask 3：$a_i\leq 3\times 10^3$。

类似 Subtask 4 枚举权值，时间复杂度 $O(\log a_i\max a_i^2)$。

结论 1：

对于任意 $x,y$ 满足 $x+y+\gcd(x,y)=\mathrm{lcm}(x,y)$，总有 $x=\frac{2}{3}y$ 或 $y=\frac{2}{3}x$。

证明 1：

不妨设 $x\leq y$。当 $x=y$ 时，原式不成立，所以 $x<y$。

因为 $x<y$，$\gcd(x,y)<y$，所以 $x+y+\gcd(x,y)<3y$。

又因为 $x+y+\gcd(x,y)>y$ 且 $\mathrm{lcm}(x,y)$ 是 $y$ 的整数倍，所以 $x+y+\gcd(x,y)=2y$，即 $\mathrm{lcm}(x,y)=2y$。

因为 $x\times y=\gcd(x,y)\times \mathrm{lcm}(x,y)$，所以 $x\times y=2y\times \gcd(x,y)$，得到 $\gcd(x,y)=\frac{x}{2}$。

带回原式得到 $x+y+\frac{x}{2}=2y$，解得 $x=\frac{2}{3}y$ 或者 $y=\frac{3}{2}x$。

推论 1.1

根据结论 1，对于每个偶数 $x$，满足 $x+y+\gcd(x,y)=\mathrm{lcm}(x,y)$ 且大于 $x$ 的 $y$ 有且只有一个，即 $y=\frac{3}{2}x$。而奇数则不存在这样的 $y$。

根据上面的结论，我们很容易得出，如果将选出来的数从小到大排序，去重，一定满足 $b_i=\frac{2}{3}b_{i+1}\ (1\leq i<k)$。

Subtask 7：无特殊限制。

因此，$O(n)$ 枚举最小值就能确定整个序列 $b$，二分或用 map 实现在 $O(\log a_i)\ /\ O(\log n)$ 的时间内查找一个数在序列 $a$ 中的出现次数，并且记录一个数是否被计算过。

每个数最多只会被计算一次，总时间复杂度：二分 $O(n\log a_i)$，map $O(n\log n)$，不过 map 常数更大一点。

值得注意的是，如果不判断一个数是否被计算过，那么时间复杂度可能会退化成 $O(n\log n\log a_i)$，只能通过 Subtask 5。

Subtask 6 是给不会二分或 map 的参赛者准备的部分分（不过可能没多大必要）。

代码如下。

#include <bits/stdc++.h>
using namespace std;

#define ll long long

const int N=3e5+5;

map <int,int> mp;
int n,a[N]; ll ans;

int main(){
	cin>>n;
	for(int i=1;i<=n;i++)cin>>a[i],mp[a[i]]++;
	sort(a+1,a+n+1);
	for(int i=1;i<=n;i++){
		ll tmp=a[i],cnt=0;
		while(mp[tmp]){
			cnt+=tmp*mp[tmp],mp[tmp]=0;
			if(tmp%2==0)tmp=tmp/2*3;
			else break;
		}
		ans=max(ans,cnt);
	} cout<<ans<<endl;
	return 0;
}