[ABC276D] Divide by 2 or 3 题解

本题的目标是通过将数列中的每个数不断除以

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$ 以外的质因数，矛盾。

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

放代码：

CPP

#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;
}

[ABC276D] Divide by 2 or 3 题解

文章操作

相关推荐

评论

[ABC276D] Divide by 2 or 3 题解