Submission #848292

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;

#define forn(i, a, n) for (int i = a; i < n; ++i)
#define ford(i, a, n) for (int i = n - 1; i >= a; --i)
#define fore(i, a, n) for (int i = a; i <= n; ++i)
#define all(a) (a).begin(), (a).end()
#define fs first
#define sn second
#define trace(a)\
	for (auto i : a) cerr << i << ' ';\
	cerr << '\n'
#define eb emplace_back

#ifndef M_PI
const ld M_PI = acos(-1.0);
#endif

const ld eps = 1e-9;
const int INF = 2000000000;
const ll LINF = 1ll * INF * INF;
const ll MOD = 1000000007;

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

int main() {
	int n;
	scanf("%d", &n);
	vector<ll> s(n);
	forn(i, 0, n) scanf("%lld", &s[i]);
	vector<int> primes;
	forn(i, 2, 1e5 + 10)
		if (isPrime(i))
			primes.eb(i);
	vector<ll> p2, p3;
	for (int i : primes) p2.eb(1ll * i * i);
	for (int i : primes) {
		ll cb = 1ll * i * i * i;
		if (cb < 1e10 + 10) p3.eb(cb);
		else break;
	}
	map<ll, int> cnt;
	for (ll x : s) {
		for (ll j : p3) {
			if (j > x) break;
			while (x % j == 0) x /= j;
		}
		cnt[x]++;
	}
	ll ans = 0;
	map<ll, char> used;
	for (auto p : cnt) {
		ll x = p.fs;
		if (used.count(x)) continue;
		if (x == 1) {
			ans += 1;
		} else {
			used[x] = 1;
			ll inv = 1, rad = 1;
			forn(j, 0, p3.size()) {
				if (x % p2[j] == 0) {
					x /= p2[j];
					inv *= primes[j];
				}
				if (x % primes[j] == 0) {
					x /= primes[j];
					rad *= primes[j];
				}
			}
			ll root = (ll)(sqrt(x) + 0.1);
			if (root * root == x) {
				auto it = lower_bound(all(primes), root);
				if (it != primes.end() && *it == root) {
					x = 1;
					inv *= root;
				}
			}
			rad *= x;
			ld res = (ld)inv * rad * rad;
			if (res > 2e10) {
				ans += p.sn;
			} else {
				inv = inv * rad * rad;
				used[inv] = 1;
				auto ptr = cnt.find(inv);
				if (ptr == cnt.end()) ans += p.sn;
				else ans += max(p.sn, ptr->sn);
			}
		}
	}
	printf("%lld\n", ans);
	return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:37:17: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
                 ^
./Main.cpp:39:36: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  forn(i, 0, n) scanf("%lld", &s[i]);
                                    ^

Judge Result