题意:有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; }
|