题解：P15621 [ICPC 2022 Jakarta R] Doubled GCD

chen_zhe · 2026-03-05 15:57:32 · 题解

这是官方题解的 AI 中文翻译

执行所有 N-1 次操作类似于求所有 A_i 的最大公约数（GCD）；但由于操作可能引入额外的 2 的因子（GCD 倍增）。

首先，从 A_i 中提取 \gcd(A)。设 B_i = A_i / GCD(A)，并设 C_i 为 B_i 中 2 的因子个数，例如 B_i = 40 = 2^3 \cdot 5，则 C_i = 3。选择两张卡 i 和 j 后，新的卡中 2 的因子个数为 \min(C_i + C_j) + 1。

因此，为了使最后一张卡 2 的因子个数最大，我们可以贪心地选择 C 中最小的两个 C_i, C_j 进行配对。设最后一张卡中 2 的因子个数为 P，最终输出为 \gcd(A) \times P。

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

const int MAXN = 1e5;

int N;
long long A[MAXN+5];
long long P[MAXN+5];
priority_queue<long long, vector<long long>, greater<long long> > PQ;

int main() {
  cin >> N;
  for (int i = 0; i < N; i++) cin >> A[i];

  long long g = A[0];
  for (int i = 1; i < N; i++) g = __gcd(g, A[i]);

  for (int i = 0; i < N; i++) A[i] /= g;

  memset(P, 0, sizeof P);
  for (int i = 0; i < N; i++) {
    while (A[i] % 2 == 0) {
      P[i]++;
      A[i] /= 2;
    }
    PQ.push(P[i]);
  }

  while (PQ.size() > 1) {
    long long p1 = PQ.top();
    PQ.pop();

    long long p2 = PQ.top();
    PQ.pop();

    PQ.push(1 + min(p1, p2));
  }

  cout << g * (1LL << PQ.top()) << endl;

}