关于三次方和三次方根的题目

题目是给你两个数 M N
1 ≤ A ≤ M
1 ≤ B ≤ N
1 ≤ M, N ≤ 10^5
然后找出有多少个A和B的组合可以算出 (3√A + 3√B )^3 是一个整数。

如果用两个循环肯定会超时的，求指教

--> A + B + 3 * (3√A * 3√B ) (3√A + 3√B)
so only 3√A and 3√B are integer, the result can be integer.
O(N)

先假设
1. A和B是整数
2. 当且仅当 (3√A + 3√B )为整数时， (3√A + 3√B )^3 才是整数

那么只要分别找到[1, M]和[1, N]之间的完全立方数的个数即可。也就是说，只要算出cube_root(M)和cube_root(N)即可。除去牛顿法，也可以使用二分法来搜索答案，方法同LCOJ上的sqrt()。时间复杂度应在O(log(max(M, N)))。考虑到M和N都不是很大的数，这个算法应该是非常快的。

ok123 发表于 2016-3-21 06:25
--> A + B + 3 * (3√A * 3√B ) (3√A + 3√B)
so only 3√A and 3√B are integer, the result can be i ...

不成立啊， A=2, B=16的时候就是反例

ccarter 发表于 2016-3-23 01:06
不成立啊， A=2, B=16的时候就是反例

真的！！！
--> A^(2/3) * B^(1/3) + A^(1/3) * B^(2/3)
any idea??

ok123 发表于 2016-3-23 02:38
真的！！！
--> A^(2/3) * B^(1/3) + A^(1/3) * B^(2/3)
any idea??

没细想。不知道对不对。
如果用p集合代表A和B的所有质因数的集合，
A=p1^r1*p2^r2*...*pn^rn
B=p1^t1*p2^t2*...*pn^tn
其中ri,ti允许为0.
如果对于任何 1<=i<=n， 都有ri %3 == ti %3，就能保证是integer。

所以对于一个给定的A，let B = p1^(r1%3) * p2^(r2%3) * ... * pn ^ (rn%3)
然后可以count += (int) cuberoot(N/B)
这是因为B, B*(2^3), B*(3^3), ... 都可以满足条件。