题解 CF573A 【Bear and Poker】
frankchenfu
2018-02-16 14:35:16
我们的目标是每个数经过任意次$\times 2$或$\times 3$之后相等,所以我们可以把每个数除以他们的公因数,然后判断这个数是不是只由$2$和$3$的因子组成。如果是,那么他们一定可以在经过有限次的$\times 2$或$\times 3$后变得相等。代码:
```
#include<cstdio>
#include<cstring>
const int MAXN=100010;
int a[MAXN];
int gcd(int x,int y)
{
return !y?x:gcd(y,x%y);
}
bool check(int x)
{
while(~x&1)
x>>=1;
while(x%3==0)
x/=3;
return x==1;
}
int main()
{
int n;scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
int _gcd=gcd(a[1],a[2]);
for(int i=3;i<=n;i++)
_gcd=gcd(_gcd,a[i]);
for(int i=1;i<=n;i++)
{
a[i]/=_gcd;
if(!check(a[i]))
{
puts("No");
return 0;
}
}
puts("Yes");
return 0;
}
```