[ABC276D] Divide by 2 or 3 题解

FFTotoro · 2022-11-06 13:00:15 · 题解

本题的目标是通过将数列中的每个数不断除以 2 或 3，来使其中每个数相等。

很显然，最终数列里唯一出现的数（记为 x），是每个数的因数。这里因为要操作数量最小，所以我们就将 x 设为所有数的最大公约数。

判断一下每个数是否可以通过只除以 2 或 3 来变成 x。即，判断每个 \dfrac{a_i}{x} 的质因数分解是否仅包含 2 或 3。

• 为什么可以将 x 设为最大公约数而不影响是否有解的判断？

  证明：若将 x 设为最大公约数时无解，则存在 a_i 使得 \dfrac{a_i}{x} 的质因数分解中包含除 2 和 3 以外的其他质因数。如果设 y 为最终数列中出现的唯一的数且合法，那么很显然 y|x\Rightarrow\left(\dfrac{a_i}{x}\right)\Big|\left(\dfrac{a_i}{y}\right)，即 \dfrac{a_i}{y} 仍然包含除 2 和 3 以外的质因数，矛盾。

  所以，利用最大公约数作为最终答案是正确的解法。

放代码：

#include<bits/stdc++.h>
using namespace std;
main(){
  ios::sync_with_stdio(false);
  int n,g,c=0; cin>>n;
  vector<int> a(n);
  for(int i=0;i<n;i++){
    cin>>a[i]; if(!i)g=a[i];
    else g=__gcd(g,a[i]); // 可以使用 __gcd 函数
  }
  for(auto &i:a){
    int x=i/g;
    while(!(x&1))x>>=1,c++;
    while(!(x%3))x/=3,c++;
    if(x>1){cout<<"-1\n"; return 0;} // 还有其他的质因数
  }
  cout<<c<<endl;
  return 0;
}