fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. int md = 998244353;
  4. int ma = 5e6 + 10;
  5. vector<int> s(ma);
  6. long long power( long long a, long long b){
  7.     a %= md;
  8.     long long res = 1;
  9.     while( b > 0 ){
  10.         if (b%2==1) res =(res *a)%md;
  11.         a = (a*a)%md;
  12.         b/=2;
  13.     }
  14.     return res;
  15. }
  16. void seive(){
  17.     for (int i = 0; i<=ma;i++) s[i] =i;
  18.     for (int i = 2; i*i <=ma;i++) {
  19.         if ( s[i] == i){
  20.             for (int j = i*i; j<=ma;j+=i) {
  21.                 if (s[j] ==j) s[j]=i;
  22.             }
  23.         }
  24.     }
  25. }
  26. vector<int> factor(int n){
  27.     vector<int> res;
  28.     while (n > 1){
  29.         int p = s[n];
  30.         res.push_back(p);
  31.         while(n%p==0) n/=p;
  32.  
  33.     }
  34.     return res;
  35. }
  36. void solve(){
  37.     int n;
  38.     cin >> n;
  39.     vector<int> a(n);
  40.     map<int, vector<int>> mp;
  41.     vector<vector<int>> adj(n);
  42.     for (int i =0; i<n;i++){
  43.         cin >> a[i];
  44.         vector<int> f = factor(a[i]);
  45.         for (int j : f){
  46.             mp[j].push_back(i);
  47.         }
  48.     }
  49.     for (auto& [p, v]: mp){
  50.         if (v.size() >2 ){
  51.             cout << 0 << endl;
  52.             return;
  53.         }
  54.         if (v.size() ==2) {
  55.             adj[v[0]].push_back(v[1]);
  56.             adj[v[1]].push_back(v[0]);
  57.         }
  58.     }
  59.     int k =0;
  60.     //BFS to find connected components and check if they are bipartite
  61.     vector<int> color(n,0);
  62.     for (int i =0; i<n;i++){
  63.         if (color[i] ==0) {
  64.             color[i] = 1;
  65.             k++;
  66.             stack<int> st;
  67.             st.push(i);
  68.             while( !st.empty()) {
  69.                 int u = st.top();
  70.                 st.pop();
  71.                 for (int v : adj[u]){
  72.                     if (color[v]==0){
  73.                         color[v]= 3 - color[u];
  74.                         st.push(v);
  75.                     }
  76.                     else if (color[v] == color[u]) {
  77.                         cout << 0 << endl;
  78.                         return;
  79.                     }
  80.                 }
  81.             }
  82.         }
  83.     }
  84.     if ( k== n) {
  85.         long long d = power(2,n) -2;
  86.         cout << d << endl;
  87.         return;
  88.     }
  89.     else cout << power(2, k) << endl;
  90.     return;
  91. }
  92.  
  93.  
  94. int main() {
  95.     ios_base::sync_with_stdio(false);
  96.     cin.tie(nullptr);
  97.     int t;
  98.     cin >> t;
  99.     seive();
  100.     while(t--) {
  101.         solve();
  102.     }
  103. }
Success #stdin #stdout 0.06s 22580KB
comments (?)
stdin
copy 
1
5
33 21 70 55 52
stdout
copy 
2
https://ideone.com/Em7fs8
language:
C++ (gcc 8.3)
created:
1 day ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!