Submission #1832970

---

Source Code Expand

%:pragma GCC optimize(2)
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <map>
#include <vector>
using namespace std;

#define int long long

const int N = 1e5 + 5;

int n , m , x , y , cnt , ans , tot;
int pr[N] , a[N] , luck[N];
bool isp[N];

map<int , int>Map;

void prework(int n) {
	memset(isp , 1 , sizeof(isp));
	isp[1] = 0;
	for(int i = 2;i <= n;++ i) {
		if(isp[i]) pr[++ cnt] = i , luck[cnt] = i * i * i;
		for(int j = 1;j <= cnt && pr[j] * i <= n;++ j) {
			isp[pr[j] * i] = 0;
			if(i % pr[j] == 0) break;
		}
	}
}

vector< pair<int,int> > Vec;

#define mp(x , y) make_pair(x , y)
#define pb push_back


void chg(int x) {
	int ano = 1 , yuan = x;
	int now;int push;
	for(register short i = 1;i <= cnt;++ i) {
		if(ano > 1e15) {
			ans ++; return;
		}
		if(x < luck[i]) {
			int y = sqrt(x);
			y --; y = max(y , 0ll);
			while(y * y < x) ++ y;
			if(y * y > x) {
				if(x <= 100000 && isp[x]) {
					if(ano * x > (1e15) / (double) x - 10) {
						ans ++;
						return;
					}
					ano *= x * x; x = 1;
					break;
				}
				else {
					ans ++; return;
				}
			}
			else {
				ano *= y;
				x = 1;
				break;
			}
		}
		if(x == 1) break;
		if(x < pr[i] * pr[i]) {
			if(x <= 100000 && isp[x]) {
				ano *= x * x;
				x = 1;
				break;
			}
			else {
				ans ++;
				return;
			}
		}
		now = luck[i];
		while(x % now == 0) x /= now , yuan /= now;
		if(x % pr[i] == 0) {
			push = pr[i] * pr[i];
			if(x % push) push = pr[i];
			x /= push;
			ano = ano * (now / push);
		}
		if(ano > 1e10) {
			ans ++; return;
		}
	}
	if(x != 1) {
		ans ++; return;
	}
	Vec.pb(mp(yuan , ano));
//	cerr << yuan << " " <<  ano << endl;
	Map[yuan] ++;
}

void dance(void) {
	for(int i = 0;i < (int) Vec.size(); ++ i) {
		if(Vec[i].first == 1 && Map[1]) {
			ans ++; Map[1] = 0;
			continue;
		}
		if(Map[Vec[i].first]) {
			ans += max(Map[Vec[i].first] , Map[Vec[i].second]);
			Map[Vec[i].first] = Map[Vec[i].second] = 0;
		}
	}
	cout << ans << endl;
}

main(void) {
//	freopen("data.txt" , "r" , stdin);
	scanf("%lld" , &n);
	for(int i = 1;i <= n;++ i) scanf("%lld" , &a[i]);
	prework(1e5 + 2);
	for(int i = 1;i <= n;++ i) {
		chg(a[i]);
//		if(i % 1000 == 0) cerr << i << endl;
	}
	dance();
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:117:20: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld" , &n);
                    ^
./Main.cpp:118:50: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  for(int i = 1;i <= n;++ i) scanf("%lld" , &a[i]);
                                                  ^

Judge Result