题意：有n个数，对于每个数有两个操作
1.把这个数乘以2
2.把这个数乘以3
操作可以重复无限次
现在问只执行这两个操作能否将所有数都变换为同一个数
如果能把这些数都变换为同一个数，那么说明这些数中的质因子除了2和3以外都相同且质因子个数都相等。因此，把所有数的关于2和3的质因子都剔除，如果所有数都相等的话那么可以变换。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <set>
#include <vector>
#include <map>
#include <queue>
#include <set>
#include <algorithm>
#include <limits>
using namespace std;
typedef long long LL;
const int MAXN=1e+5 + 1000;
const int INF = numeric_limits<int>::max();
const LL LL_INF= numeric_limits<LL>::max();
int n;LL A[MAXN];
LL lcm(LL a,LL b){
return a*b/__gcd(a,b);
}
int main()
{
while(~scanf("%d",&n)){
for(int i=1;i<=n;i++){
scanf("%I64d",&A[i]);
while(A[i]%2==0)A[i]/=2;
while(A[i]%3==0)A[i]/=3;
}
LL t=A[1];
int flag=0;
for(int i=1;i<=n;i++){
if(t!=A[i])flag=1;
}
if(flag)puts("No");
else puts("Yes");
}
return 0;
}
|
