結果

問題 No.917 Make One With GCD
コンテスト
ユーザー alexara1123
提出日時 2019-10-25 23:09:58
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 4,283 bytes
コンパイル時間 1,140 ms
コンパイル使用メモリ 111,292 KB
実行使用メモリ 6,948 KB
最終ジャッジ日時 2024-09-13 07:17:11
合計ジャッジ時間 2,206 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 13 WA * 19
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <cstring>
#include <queue>
#include <set>
#include <unordered_set>
#include <unordered_map>
#include <map>
#include <numeric>
#include <functional>
#include <cmath>
#include <cassert>
#include <string>
#include <iostream>

using namespace std;
typedef long long ll;
typedef pair<int, int> P;
typedef pair<ll, ll> PL;
ll MOD = 1000000007;
const int mod = 1000000007;
ll INF = 1LL << 60;

template <typename T>
istream &operator>>(istream &is, vector<T> &vec)
{
   for (auto &v : vec)
      is >> v;
   return is;
}
template <typename T>
ostream &operator<<(ostream &os, const vector<T> &vec)
{
   os << "[";
   for (auto v : vec)
      os << v << ",";
   os << "]";
   return os;
}
template <typename T>
ostream &operator<<(ostream &os, const deque<T> &vec)
{
   os << "deq[";
   for (auto v : vec)
      os << v << ",";
   os << "]";
   return os;
}
template <typename T>
ostream &operator<<(ostream &os, const set<T> &vec)
{
   os << "{";
   for (auto v : vec)
      os << v << ",";
   os << "}";
   return os;
}
template <typename T>
ostream &operator<<(ostream &os, const unordered_set<T> &vec)
{
   os << "{";
   for (auto v : vec)
      os << v << ",";
   os << "}";
   return os;
}
template <typename T>
ostream &operator<<(ostream &os, const multiset<T> &vec)
{
   os << "{";
   for (auto v : vec)
      os << v << ",";
   os << "}";
   return os;
}
template <typename T>
ostream &operator<<(ostream &os, const unordered_multiset<T> &vec)
{
   os << "{";
   for (auto v : vec)
      os << v << ",";
   os << "}";
   return os;
}
template <typename T1, typename T2>
ostream &operator<<(ostream &os, const pair<T1, T2> &pa)
{
   os << "(" << pa.first << "," << pa.second << ")";
   return os;
}
template <typename TK, typename TV>
ostream &operator<<(ostream &os, const map<TK, TV> &mp)
{
   os << "{";
   for (auto v : mp)
      os << v.first << "=>" << v.second << ",";
   os << "}";
   return os;
}
template <typename TK, typename TV>
ostream &operator<<(ostream &os, const unordered_map<TK, TV> &mp)
{
   os << "{";
   for (auto v : mp)
      os << v.first << "=>" << v.second << ",";
   os << "}";
   return os;
};
#define dbg(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ") " << __FILE__ << endl;
template <typename A, size_t N, typename T>
void Fill(A (&array)[N], const T &val)
{
   fill((T *)array, (T *)(array + N), val);
}

vector<bool> prime_table(int n)
{
   vector<bool> prime(n + 1, true);
   if (n >= 0)
      prime[0] = false;
   if (n >= 1)
      prime[1] = false;
   for (int i = 2; i * i <= n; i++)
   {
      if (!prime[i])
         continue;
      for (int j = i + i; j <= n; j += i)
      {
         prime[j] = false;
      }
   }
   return prime;
}

bool is_prime(int64_t x)
{
   for (int64_t i = 2; i * i <= x; i++)
   {
      if (x % i == 0)
         return false;
   }
   return true;
}

ll a[60];
int solve()
{
   ll n;
   cin >> n;
   for(int i=0; i < n; i++){
      cin >> a[i];
   }
   map<ll, ll> m;
   map<ll, ll> mmm;
   set<ll> s;
   ll cnt = 0;
   for(int i=0; i < n; i++){
      if(a[i] > 1){
         cnt++;
      }
      for(int j=0; j < n; j++){
         if(i == j){
            continue;
         }
         s.insert(__gcd(a[i],a[j]));
      }
   }
   // cout << s << endl;
   vector<bool> check(n);
   for(auto it=s.begin();it != s.end();it++){
      if(!is_prime(*it)){
         continue;
      }
      for(int i=0; i < n; i++){
         if(a[i] % *it == 0  && *it > 1){
            if(!check[i]){
               check[i] = true;
               m[*it]++;
            }else{
               mmm[*it]++;
            }
      }
     }
   }
   // cout << check << endl;




   ll ans = (1LL << n) - 1;
   ll z = 0;
   for(auto it=s.begin();it != s.end();it++){
      // dbg(*it);
      // dbg(m[*it]);

      if(m[*it] > 0 && *it != 1){
            // dbg((1LL << m[*it]));
            if(mmm[*it] == 0){
            ans -= (1LL << (m[*it])) - 1 - m[*it];
            }else{
               ans -= (1LL << (m[*it] + mmm[*it])) - (1LL << (mmm[*it])) - m[*it];
            }
            //cnt -= m[*it];
            
      }
   }

   cout << ans - cnt<< endl;

   return 0;
}
int main()
{
   ios::sync_with_stdio(false);
   cin.tie(0);

   solve();
}
0