Submission #846858

---

Source Code Expand

#include <bits/stdc++.h>

using namespace std;

#define REP(i, a, b) for (int i = (a), i##_end_ = (b); i < i##_end_; ++i)
#define debug(...) fprintf(stderr, __VA_ARGS__)
#define mp make_pair
#define x first
#define y second
#define pb push_back
#define SZ(x) (int((x).size()))
#define ALL(x) (x).begin(), (x).end()

#ifdef __WIN32
#define LLFORMAT "I64"
#define Rand() ((rand() << 15) | rand())
#else
#define LLFORMAT "ll"
#define Rand() (rand())
#endif

template<typename T> inline bool chkmin(T &a, const T &b) { return a > b ? a = b, 1 : 0; }
template<typename T> inline bool chkmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; }

typedef long long LL;

const int oo = 0x3f3f3f3f;

LL mul(LL b, LL e, LL m)
{
	b %= m;
	e %= m;
	LL t = b * e - LL((long double)b * e / m) * m;
	while (t < 0) t += m;
	while (t >= m) t -= m;
	return t;
}
 
LL Fpm(LL b, LL e, LL m)
{
	LL t = 1;
	for ( ; e; e >>= 1, b = mul(b, b, m))
		if (e & 1) t = mul(t, b, m);
	return t;
}
 
bool witness(int a, LL b)
{
	if (a == b) return 1;
	LL s = b - 1;
	int cnt = 0;
	while (!(s & 1)) s >>= 1, ++cnt;
	LL tmp = Fpm(a, s, b);
	if (tmp == 1) return 1;
	while (cnt)
	{
		if (tmp == b - 1) return 1;
		--cnt;
		tmp = mul(tmp, tmp, b);
		if (tmp == 1) return 0;
	}
	return 0;
}
 
const int p[] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31}, pn = sizeof(p) / sizeof(p[0]);

bool isprime(LL x)
{
	if (!x) return 0;
	if (x == 1) return 0;
	REP(i, 0, pn) 
	{
		if (!witness(p[i], x)) return 0;
	}
	return 1;
}

set<LL> all;

inline void rho(LL x)
{
	if (isprime(x))
	{
		all.insert(x);
		return;
	}
	if (x <= 100000000)
	{
		for (int i = 2; i * i <= x; ++i)
		{
			if (!(x % i)) all.insert(i);
			while (!(x % i)) x /= i;
		}
		if (x > 1) all.insert(x);
		return;
	}
	while (1)
	{
		LL x0 = 0, x1 = 0;
		int c = Rand();
		LL d = 1;
		int cnt = 0;
		while (d == 1)
		{
			x0 = mul(x0, x0, x);
			(x0 += c) %= x;
			d = __gcd(abs(x0 - x1), x);
			++cnt;
			if (!(cnt & (cnt - 1))) x1 = x0;
		}
		if (d != x)
		{
			rho(d);
			rho(x / d);
			break;
		}
	}
}

inline void decom(LL x)
{
	all.clear();
	REP(i, 0, pn)
	{
		if (!(x % p[i])) all.insert(p[i]);
		while (!(x % p[i])) x /= p[i];
	}
	if (x > 1) rho(x);
}

const int maxn = 100000;

int n;
LL a[maxn + 5];

map<vector<pair<LL, int> >, int> num;

int main()
{
#ifdef matthew99
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif
	scanf("%d", &n);
	int ret = 0;
	REP(i, 0, n) 
	{
		scanf("%" LLFORMAT "d", a + i);
		decom(a[i]);
		vector<pair<LL, int> > tmp;
		for (auto u : all)
		{
			int cnt = 0;
			while (!(a[i] % u)) a[i] /= u, ++cnt;
			cnt %= 3;
			if (cnt) tmp.pb(mp(u, cnt));
		}
		if (SZ(tmp)) ++num[tmp];
		else ret = 1;
	}
	for (auto u : num) if (u.y)
	{
		vector<pair<LL, int> > tmp;
		for (auto v : u.x) tmp.pb(mp(v.x, 3 - v.y));
		if (num.count(tmp))
		{
			int val = num[tmp];
			ret += max(u.y, val);
			num[tmp] = 0;
		}
		else ret += u.y;
	}
	printf("%d\n", ret);
	return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:144:17: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
                 ^
./Main.cpp:148:33: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%" LLFORMAT "d", a + i);
                                 ^

Judge Result