#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; typedef long long ll; typedef pair P; typedef pair PL; ll MOD = 1000000007; const int mod = 1000000007; ll INF = 1LL << 60; template istream &operator>>(istream &is, vector &vec) { for (auto &v : vec) is >> v; return is; } template ostream &operator<<(ostream &os, const vector &vec) { os << "["; for (auto v : vec) os << v << ","; os << "]"; return os; } template ostream &operator<<(ostream &os, const deque &vec) { os << "deq["; for (auto v : vec) os << v << ","; os << "]"; return os; } template ostream &operator<<(ostream &os, const set &vec) { os << "{"; for (auto v : vec) os << v << ","; os << "}"; return os; } template ostream &operator<<(ostream &os, const unordered_set &vec) { os << "{"; for (auto v : vec) os << v << ","; os << "}"; return os; } template ostream &operator<<(ostream &os, const multiset &vec) { os << "{"; for (auto v : vec) os << v << ","; os << "}"; return os; } template ostream &operator<<(ostream &os, const unordered_multiset &vec) { os << "{"; for (auto v : vec) os << v << ","; os << "}"; return os; } template ostream &operator<<(ostream &os, const pair &pa) { os << "(" << pa.first << "," << pa.second << ")"; return os; } template ostream &operator<<(ostream &os, const map &mp) { os << "{"; for (auto v : mp) os << v.first << "=>" << v.second << ","; os << "}"; return os; } template ostream &operator<<(ostream &os, const unordered_map &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 void Fill(A (&array)[N], const T &val) { fill((T *)array, (T *)(array + N), val); } vector prime_table(int n) { vector 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 m; map mmm; set 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 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(); }