題干：

Limak is an old brown bear. He often plays poker with his friends. Today they went to a casino. There are?n?players (including Limak himself) and right now all of them have bids on the table.?i-th of them has bid with size?ai?dollars.

Each player can double his bid any number of times and triple his bid any number of times. The casino has a great jackpot for making all bids equal. Is it possible that Limak and his friends will win a jackpot?

Input

First line of input contains an integer?n?(2?≤?n?≤?105), the number of players.

The second line contains?n?integer numbers?a1,?a2,?...,?an?(1?≤?ai?≤?109) — the bids of players.

Output

Print "Yes" (without the quotes) if players can make their bids become equal, or "No" otherwise.

Examples

Input

4 75 150 75 50

Output

Yes

Input

3 100 150 250

Output

No

Note

In the first sample test first and third players should double their bids twice, second player should double his bid once and fourth player should both double and triple his bid.

It can be shown that in the second sample test there is no way to make all bids equal.

題目大意：

? ?最開始每個人都有一個值，任何一個人都可以將自己的值變成原來的兩倍或三倍，問能不能讓所有人的值都相等。

解題報告：

? ?除了暴力想不到別的方法了，，隨便交一發沒想到a了。。不過不會算時間復雜度？感覺o(n^2)級別的吧？本來想先把a[i]都存下，然后再o(n)判斷一遍的，但是感覺可能會超時？(畢竟不會算復雜度)于是采取邊處理便判斷的方式，找到NO的就直接輸出然后結束程序了，算是一種剪枝？

? ?至于這道題的思路，也挺好想的吧算是。我們分析最終得數，如果最終得數要相同，因為可以乘任意次，也就是說最終得數中可以包含任意個3和2做因子，于是我們把這些因子除去，看剩下的數字是否是一樣的，也就可以判斷最終的答案是否是一樣的。

法2：人選兩個人出來，a1,a2,按題意方法要有所以直接判斷a1,a2能不能不斷的乘2,3得到兩個數的最小公倍數就好了。

AC代碼：

//暴力？ #include<bits/stdc++.h>using namespace std; const int MAX = 1e5 +5; int a[MAX]; int main() {int n;cin>>n;for(int i = 1; i<=n; i++) scanf("%d",a+i);for(int i = 1; i<=n; i++) {while(a[i]%6==0) a[i]/=6;while(a[i]%2==0) a[i]/=2;while(a[i]%3==0) a[i]/=3;if(i==1) continue;if(a[i] != a[i-1]) {puts("No");return 0;}}puts("Yes");return 0 ;}

?

總結

以上是生活随笔為你收集整理的【CodeForces - 574C】Bear and Poker（思维，剪枝，数学）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。