fork(2) download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. const int kMaxV = 2e5;
  6.  
  7. struct DisjointSets {
  8.     DisjointSets(int n=kMaxV+1)
  9.         : parent(n, -1),
  10.           weight(n, 0),
  11.           to(n, -1)
  12.     { }
  13.  
  14.     void MarkActive(const int id) {
  15.         if (parent[id] == -1) {
  16.             parent[id] = id;
  17.             weight[id] = 1;
  18.             to[id] = id;
  19.         }
  20.     }
  21.  
  22.     int operator [](const int id) const {
  23.         return parent[id];
  24.     }
  25.  
  26.     void Unite(int a, int b) {
  27.         a = (*this)[a]; b = (*this)[b];
  28.         if (a == b) {
  29.             return;
  30.         }
  31.  
  32.         if (weight[a] < weight[b]) {
  33.             swap(a, b);
  34.         }
  35.         parent[b] = a;
  36.         weight[a] += weight[b];
  37.  
  38.         int it = b;
  39.         do {
  40.             parent[it] = a;
  41.             it = to[it];
  42.         } while (it != b);
  43.         swap(to[b], to[a]);
  44.     }
  45.  
  46.     int Weight(const int node) const {
  47.         return weight[(*this)[node]];
  48.     }
  49.  
  50.     bool Singleton(const int node) const {
  51.         return Weight(node) == 1;
  52.     }
  53.  
  54.     vector<int> parent, weight, to;
  55. } dsu;
  56.  
  57. int divisor[kMaxV + 1];
  58. int node_weight[kMaxV + 1];
  59.  
  60. vector<int> active;
  61. int pos_in_active[kMaxV + 1], num_active[kMaxV + 1];
  62. bool erased[kMaxV + 1];
  63.  
  64. vector<int> values[kMaxV + 1];
  65. vector<int> primes;
  66.  
  67. void Init() {
  68.     for (int i = 2; i <= kMaxV; ++i) {
  69.         if (divisor[i]) {
  70.             continue;
  71.         }
  72.  
  73.         divisor[i] = i;
  74.         primes.push_back(i);
  75.         for (int j = 2 * i; j <= kMaxV; j += i) {
  76.             divisor[j] = i;
  77.         }
  78.     }
  79. }
  80.  
  81. void Backtrack(int num, int pos) {
  82.     if (pos == (int)primes.size() or num > kMaxV / primes[pos]) {
  83.         return;
  84.     }
  85.     Backtrack(num, pos + 1);
  86.  
  87.     // erase primes[pos]
  88.     vector<int> changes;
  89.     for (auto it : values[primes[pos]]) {
  90.         if (not erased[it]) {
  91.             erased[it] = true;
  92.  
  93.             --num_active[dsu[it]];
  94.             if (num_active[dsu[it]] == 0) {
  95.                 pos_in_active[active.back()] = pos_in_active[dsu[it]];
  96.                 swap(active[pos_in_active[active.back()]], active.back());
  97.                 pos_in_active[dsu[it]] = -1;
  98.                 active.pop_back();
  99.             }
  100.  
  101.             changes.push_back(it);
  102.         }
  103.     }
  104.  
  105.     num *= primes[pos];
  106.     if (node_weight[num] > 0 and not active.empty()) {
  107.         if (num_active[dsu[num]] == 0) {
  108.             active.push_back(num);
  109.         }
  110.  
  111.         int new_num_active = num_active[dsu[active[0]]];
  112.         for (int i = 1; i < (int)active.size(); ++i) {
  113.             new_num_active += num_active[dsu[active[i]]];
  114.             dsu.Unite(active[i - 1], active[i]);
  115.         }
  116.  
  117.         int comp = dsu[active[0]];
  118.         active.clear();
  119.         active.push_back(comp);
  120.         pos_in_active[comp] = 0;
  121.         num_active[comp] = new_num_active;
  122.     }
  123.  
  124.     Backtrack(num, pos + 1);
  125.  
  126.     // undo erase
  127.     for (auto it : changes) {
  128.         erased[it] = false;
  129.         ++num_active[dsu[it]];
  130.         if (pos_in_active[dsu[it]] == -1) {
  131.             pos_in_active[dsu[it]] = (int)active.size();
  132.             active.push_back(dsu[it]);
  133.         }
  134.     }
  135.     changes.clear();
  136. }
  137.  
  138. int main() {
  139.     cin.tie(nullptr);
  140.     ios_base::sync_with_stdio(false);
  141.  
  142.     Init();
  143.  
  144.     int n; cin >> n;
  145.     for (int i = 0; i < n; ++i) {
  146.         int x; cin >> x;
  147.         if (x == 1) {
  148.             cout << 1 << endl;
  149.             return 0;
  150.         }
  151.  
  152.         int last = -1, square_free_form = 1;
  153.         vector<int> prime_divisors;
  154.         while (x > 1) {
  155.             if (divisor[x] != last) {
  156.                 square_free_form *= divisor[x];
  157.                 last = divisor[x];
  158.                 prime_divisors.push_back(divisor[x]);
  159.             }
  160.             x /= divisor[x];
  161.         }
  162.         for (auto it : prime_divisors) {
  163.             values[it].push_back(square_free_form);
  164.         }
  165.         ++node_weight[square_free_form];
  166.     }
  167.  
  168.     for (int i = 2; i <= kMaxV; ++i) {
  169.         if (node_weight[i] == 0) {
  170.             continue;
  171.         }
  172.  
  173.         sort(values[i].begin(), values[i].end());
  174.         values[i].erase(
  175.             unique(values[i].begin(), values[i].end()), values[i].end());
  176.  
  177.         dsu.MarkActive(i);
  178.         num_active[i] = 1;
  179.         pos_in_active[i] = (int)active.size();
  180.         active.push_back(i);
  181.     }
  182.  
  183.     Backtrack(1, 0);
  184.  
  185.     int num_components = 0;
  186.     for (int i = 2; i <= kMaxV; ++i) {
  187.         if (node_weight[i] == 0 or dsu[i] != i) {
  188.             continue;
  189.         }
  190.  
  191.         if (dsu.Singleton(i)) {
  192.             num_components += node_weight[i];
  193.         } else {
  194.             ++num_components;
  195.         }
  196.     }
  197.  
  198.     cout << num_components << endl;
  199. }
Success #stdin #stdout 0s 25776KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/N11lPY
language:
C++14 (gcc 8.3)
created:
5 years 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!