こちらはすんなり解けた。
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のおかげもあって方針には迷わなかった。