kmjp's blog

競技プログラミング参加記です

CSAcademy Round #13 : D. Num Cube Sets

こちらはすんなり解けた。
https://csacademy.com/contest/round-13/#task/num-cube-sets

問題

2つの数列A,Bがある。
A,Bの部分集合A'、B'を作ったとき、a∈A'、b∈B'に対しa*bが必ず立方数になるようにしたい。

A' ^2+ B' ^2の最大値を求めよ。

解法

この問題と似ている。
AtCoder AGC #003 : D - Anticube - kmjp's blog

A,Bの各要素を立方数で割っていった値で分類する。
P(x) := Aの要素を立方数で割っていったときxとなる要素数
Q(y) := Bの要素を立方数で割っていったときyとなる要素数

あとはxを総当たりし、P(x)^2+Q(z)^2の最大値を求める。
zはxと掛けると立方数になる最小値。
上記AGCではxが大きいため、xからzをトリッキーな方法で解いたが、今回はxが小さいので素因数分解した。

const int prime_max = 1000005;
int NP,prime[100000],divp[prime_max];

void cprime() {
	for(int i=2;i<prime_max;i++) if(divp[i]==0) {
		divp[i]=i;
		for(ll j=1LL*i*i;j>i&&j<prime_max;j+=i) divp[j]=i;
	}
}

int T;
int N,M;
int A[505050],B[505050];
int C[1010101];

ll getrev(ll v) {
	ll r=1;
	while(v>1) {
		if(r%divp[v]==0) r/=divp[v];
		else r*=divp[v]*divp[v];
		v /= divp[v];
	}
	return r;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cprime();
	
	for(i=1;i<=1000000;i++) C[i]=i;
	for(i=2;i<=100;i++) {
		for(x=i*i*i;x<=1000000;x+=i*i*i) C[x]=x/(i*i*i);
	}
	
	cin>>T;
	while(T--) {
		cin>>N>>M;
		map<ll,ll> AM,BM;
		FOR(i,N) cin>>x, AM[C[x]]++;
		FOR(i,M) cin>>x, BM[C[x]]++;
		
		ll ret=-1;
		if(AM.count(1)&&BM.count(1)) ret=AM[1]*AM[1]+BM[1]*BM[1];
		FORR(r,AM) if(r.first>1) {
			ll a=r.first;
			ll b=getrev(a);
			if(BM.count(b)) ret=max(ret,AM[a]*AM[a]+BM[b]*BM[b]);
		}
		
		cout<<ret<<endl;
		
	}
}

まとめ

AGCのおかげもあって方針には迷わなかった。