题解 CF573A【Bear and Poker】
Rbu_nas
2019-04-13 22:28:48
题意:
有 $n$ 个数 $a_i$,你可以把每个数任意次 $\times2$ 或 $\times3$,问能否最终使得每个数相等。
一道不算难想的数学模拟题,对于给出的数列 $a_1,\ a_2,\ a_3\ ... \ a_n$,我们将结果视为是由数列 $b_1×k_1\ ,\ b_2×k_2\ ,\ b_3×k_3\ \ ... \ \ b_n×k_n$ 得到的,如果能通过 $\times2$ 或 $\times3$ 使 $a[]$ 数组相等,那么 $b[]$ 数组一定能通过除法使 $b_1,\ b_2,\ b_3\ ... \ b_n$ 相等。
由于 $b[]$ 中的元素的系数不同,把它视为 $2$ 与 $3$ 的倍数,若是最后 $b_1,\ b_2,\ b_3\ ... \ b_n$ 不同,那么它们通过 $\times k$ 即$\times2n$ $\times3n$ ($n>=0$) 也不能相等,这个道理并不难懂,那么代码也十分简单了。
```cpp
#include <bits/stdc++.h>
using namespace std;
#define gcc getchar
template <typename T> inline void read(T&x)
{
x=0; bool f=true; char ck=gcc();
for( ; ck<'0'||ck>'9'; ck=gcc()) if(ck == '-') f=false;
for( ; ck>='0'&&ck<='9'; ck=gcc()) x=(x<<1)+(x<<3)+(ck^48);
x=f?x:-x; return ;
}
#define N 100003
int n, a[N];
int main(void)
{
read(n);
for(int i=1; i<=n; ++i) read(a[i]);
for(int i=1; i<=n; ++i)
{
while(!(a[i] % 2)) a[i]/=2;
while(!(a[i] % 3)) a[i]/=3;
//通过不断除法使每个ai都化为无系数bi
}
for(int i=1; i<n; ++i)
if(a[i] != a[i+1])
{
puts("No");
//显然,如果有一个bi不等就不行
return 0;
}
puts("Yes");
return 0;
}
```