题解 CF573A【Bear and Poker】

Rbu_nas

2019-04-13 22:28:48

Solution

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