题解 P6786 【「SWTR-6」GCDs & LCMs】

· · 题解

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

题面传送门。

题意简述：从给定序列 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;
}