frankchenfu 的博客

frankchenfu 的博客

题解 CF573A 【Bear and Poker】

posted on 2018-02-16 14:35:16 | under 题解 |

我们的目标是每个数经过任意次$\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;
}