AGC003E: Anticube

https://agc003.contest.atcoder.jp/tasks/agc003_d

本質を勘違いした…

まず素数のうちa個あるものはa%3個にしてよいです。それでvをcubeにする値uをつなげたグラフを考えると二部グラフになるので、max( (vの数),(uの数) )の合計を求める問題に帰着できます。

しかし、vの素因数分解を愚直にやるとO(sqrt(s)N)になって間に合いません。
なので次のように工夫するとうまく行きます。

• 3000までの素数は愚直に求めて、3000までの素数を取り除いた状態の数をaとする。aが平方数ならsqrt(a)を要素に加えて、そうでなければ素数とみなす。

証明
3000^3>=10^10なのでaには3000以上の素数が3つ以上含まれることはありません。ということで、aは(1)素数が1つ,(2)異なる素数が2つ(3)同じ素数のいずれかに素因数分解されることがわかります。
(1)の場合は問題ありません。
(2)の場合もaとペアになるのはa^2(>=3000^4>=10^10)となるので素数とみなしてもペアが存在せず問題ないです。
(3)の場合もaが平方数か考えるので問題ないです。

これで3000というのは大体O(s^(1/3))なのでO(s^(1/3)N)となりギリギリ間に合います。

普通にデータ構造パートでTLEしているのかと思っていろいろ無駄なことしてしまった…。

void update(pl& p, ll a, int cnt) {
	if(cnt == 1) {
		p.fst *= a;
		p.sec *= a * a;
	}
	else {
		p.fst *= a * a;
		p.sec *= a;
	}
}

bool ok(ll a, ll b) {
	int cnt = 0;
	while(a >= 10) {
		a /= 10; cnt++;
	}
	while(b >= 10) {
		b /= 10; cnt++;
	}
	return cnt <= 10;
}

pl ntn(ll a) {
	map<ll, int> res;
	for(ll i = 2; i <= 3000; i++) {
		while(a % i == 0) {
			res[-i]++;
			a /= i;
		}
	}
	ll sa = ll(sqrt(a) + eps);
	if(a != 1) {
		if(a == sa * sa) res[-sa] += 2;
		else res[-a]++;
	}
	// debug(vector<pl>(all(res)));

	pl pre1 = pl(1, 1);
	pl pre2 = pl(1, 1);
	bool fst = true;
	for(auto p : res) {
		p.sec %= 3;
		if(p.sec == 0) continue;
		ll v = -p.fst;
		if(fst) {
			update(pre1, v, p.sec);
			fst = false;
		}
		else update(pre2, v, p.sec);
	}
	// debug(pre1, pre2);
	if(ok(pre1.sec, pre2.sec)) {
		return pl(pre1.fst * pre2.fst, pre1.sec * pre2.sec);
	}
	else return pl(pre1.fst * pre2.fst, -1);
}

int N;
map<pl, int> G;

void solve() {
	cin >> N;
	rep(i, 0, N) {
		ll a; cin >> a;
		G[ntn(a)]++;
	}

	int cnt = 0;
	for(auto pp : G) {
		// debug(pp);
		pl pt = pp.fst;
		int v = pp.sec;
		if(pt == pl(1, 1)) cnt += 2;
		else if(pt.sec == -1) cnt += v * 2;
		else {
			swap(pt.fst, pt.sec);
			if(G.find(pt) != G.end()) {
				int w = G[pt];
				cnt += max(v, w);
			}
			else cnt += v * 2;
		}
	}
	cout << cnt / 2 << "\n";
}

なんか3000じゃなくて400でも通ったんだけどどうしてだろう…