Submission #846668

---

Source Code Expand

#include <cstdio>
#include <cstdlib>
#include <cassert>
#include <iostream>
#include <set>
#include <vector>
#include <cstring>
#include <string>
#include <algorithm>
#include <numeric>
#include <cmath>
#include <complex>
#include <map>
#include <queue>
#include <array>
#include <bitset>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vi> vvi;
typedef vector<vl> vvl;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef pair<double, double> pdd;
typedef vector<string> vs;

int main() {
  vi erat(1000000, 1);
  erat[0] = erat[1] = 0;
  for (int i = 2; i * i < erat.size(); ++i) if (erat[i]) {
    for (int j = i * i; j < erat.size(); j += i) erat[j] = 0;
  }
  int n;
  scanf("%d", &n);
  vi p;
  for (int i = 2; i <= 2500; ++i) {
    p.push_back(i);
    for (int j = 2; j * j <= i; ++j) if (i % j == 0) {
      p.pop_back();
      break;
    }
  }
  vl p3;
  for (ll d : p) p3.push_back(d*d*d);
  int was1 = 0;
  vl a;
  for (int i = 0; i < n; ++i) {
    ll x;
    scanf("%lld", &x);
    for (ll d3 : p3) {
      if (d3 > x) break;
      while (x % d3 == 0) x /= d3;
    }
    if (x == 1) {
      was1 = 1;
    } else {
      a.push_back(x);
    }
  }
  sort(a.begin(), a.end());
  if (a.empty()) {
    cout << was1 << endl;
    return 0;
  }
  vl v(1, a[0]);
  vi c(1, 1);
  for (int i = 1; i < a.size(); ++i) {
    if (a[i] == a[i-1]) ++c.back();
    else {
      v.push_back(a[i]);
      c.push_back(1);
    }
  }
  vi was(v.size());
  int res = was1;
//  cerr << was1 << endl;
  for (int i = 0; i < v.size(); ++i) if (!was[i]) {
//    cerr << v[i] << ' ' << c[i] << endl;
    was[i] = 1;
    ll r = 1;
    ll val = v[i];
    for (int it = 0; it < p.size() && p3[it] <= val; ++it) if (val % p[it] == 0) {
      ll mul = p3[it];
      while (val % p[it] == 0) {
        val /= p[it];
        mul /= p[it];
      }
      if (r <= 1e15 / mul) r *= mul;
    }
    if (val > 1) {
      ll sq = sqrt(val);
      while (sq * sq < val) ++sq;
      while (sq * sq > val) --sq;
      if (sq * sq == val) {
        assert(erat[sq]);
        val = 1;
        if (r <= 1e15 / sq) r *= sq;
      }
    }
    if (val > 1 && val <= 1000000) {
      ll mul = val * val;
      if (r <= 1e15 / mul) r *= mul;
      val = 1;
    }
    if (val > 1 || !binary_search(v.begin(), v.end(), r)) {
      res += c[i];
    } else {
      int it = lower_bound(v.begin(), v.end(), r) - v.begin();
      was[it] = 1;
      res += max(c[i], c[it]);
    }
  }
  printf("%d\n", res);
  return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:35:18: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &n);
                  ^
./Main.cpp:50:22: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
     scanf("%lld", &x);
                      ^

Judge Result