Submission #846205

---

Source Code Expand

#include <cstdio>
#include <cassert>
#include <map>
#include <vector>
#include <cmath>
#include <set>
using namespace std;

typedef long long llong;

const llong MAX = pow(1e10, 1.0 / 3) + 10;
const int MAX2 = 1e5 + 10;

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

vector<llong> prime_cubes;
vector<int> primes;
void build_primes() {
    for (int i = 2; i < MAX; i++) {
        if (is_prime(i))
            prime_cubes.push_back(1ll * i * i * i);
    }
    for (int i = 2; i < MAX2; i++) {
        if (is_prime(i))
            primes.push_back(i);
    }
}

llong norm(llong x) {
    for (llong q : prime_cubes) {
        if (q > x)
            break;
        while (x % q == 0)
            x /= q;
    }
    return x;
}

const llong inf = 1e12;

llong mul(llong a, llong b) {
    if (inf / b < a)
        return inf;
    else
        return a * b;
}

llong contr(llong x) {
    llong y = 1;
    for (int p : primes) {
        if (1ll * p * p > x)
            break;
        if (x % p == 0) {
            if (((x / p) % p) == 0)
                y = mul(y, p), x /= p, x /= p;
            else
                y = mul(y, mul(p, p)), x /= p;
        }
    }
    if (x != 1)
        y = mul(y, mul(x, x));
    return y;
}

int main() {
    int n;
    scanf("%d", &n);
    build_primes();
    map<llong, int> cnt;
    for (int i = 0; i < n; i++) {
        llong x;
        scanf("%lld", &x);
        x = norm(x);
        cnt[x]++;
    }
    int ans = 0;
    set<llong> used;
    for (auto pr : cnt) {
        llong x = pr.first;
        int c = pr.second;
        llong y = contr(x);
        if (used.count(x))
            continue;
        if (x == y) {
            assert(x == 1);
            ans += 1;
        } else {
            if (cnt.count(y)) {
                ans += max(c, cnt[y]);
                used.insert(y);
                used.insert(x);
            } else {
                used.insert(x);
                ans += c;
            }
        }
    }
    printf("%d\n", ans);
}

Submission Info

Compile Error

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

Judge Result