首页 > 代码库 > Codeforce 573A. Bear and Poker

Codeforce 573A. Bear and Poker

Limak is an old brown bear. He often plays poker with his friends. Today they went to a casino. There are nplayers (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.

将2将3除尽,剩下的数如果一致即可

技术分享
#include <cstdio>
#include <cctype>
#include <stdlib.h>
#include <iostream>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <string>
#include <vector>
#include <map>
using namespace std;
typedef long long LL;
int n;
LL times = 0;

int main() {
  // freopen("test.in","r",stdin);
  cin >> n;
  LL a;
  cin >> a;
  int ok = 1;
  while (a > 1 && a % 2 == 0){
    a = a / 2;
  }
  while (a > 1 && a % 3 == 0){
    a = a / 3;
  }
  times = a;
  for (int i=1;i<n;i++){
    LL b;
    cin >> b;
    if (!ok) continue;
    if (b % times != 0){
      ok = 0; continue;
    }
    else {
      b = b / times;
      while (b > 1 && b % 2 == 0){
        b = b / 2;
      }
      while (b > 1 && b % 3 == 0){
        b = b / 3;
      }
      if (b > 1){
        ok = 0; continue;
      }
    }
  }
  if (ok) cout << "Yes";
  else cout << "No";
  return 0;
}
View Code

 

Codeforce 573A. Bear and Poker