传送门
把每一个数aaa质因数分解。
假设a=p1a1∗p2a2∗...∗pkaka=p_1^{a_1}*p_2^{a_2}*...*p_k^{a_k}a=p1a1∗p2a2∗...∗pkak
然后可以转化成a′=p1a1mod3∗p2a2mod3∗...∗pkakmod3a'=p_1^{a_1mod3}*p_2^{a_2mod3}*...*p_k^{a_kmod3}a′=p1a1mod3∗p2a2mod3∗...∗pkakmod3
然后可以找到另外一个不含立方因子的bbb使得a∗ba*ba∗b是一个立方数。
显然(a,b)(a,b)(a,b)这一对数我们最多只能选其中一个。
因此贪心选就行了。
代码