一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 1380|回复: 5
收起左侧

[算法题] 关于三次方和三次方根的题目

[复制链接] |试试Instant~ |关注本帖
alanyip 发表于 2016-3-20 21:35:19 | 显示全部楼层 |阅读模式

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

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

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

ok123 发表于 2016-3-21 06:25:51 | 显示全部楼层
--> 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 反对 1

使用道具 举报

stellari 发表于 2016-3-22 12:00:41 | 显示全部楼层
先假设
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都不是很大的数,这个算法应该是非常快的。

回复 支持 反对

使用道具 举报

ccarter 发表于 2016-3-23 01:06:29 | 显示全部楼层
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的时候就是反例
回复 支持 反对

使用道具 举报

ok123 发表于 2016-3-23 02:38:39 | 显示全部楼层
ccarter 发表于 2016-3-23 01:06
不成立啊, A=2, B=16的时候就是反例

真的!!!
--> A^(2/3) * B^(1/3) + A^(1/3) * B^(2/3)
any idea??
回复 支持 反对

使用道具 举报

ccarter 发表于 2016-3-23 03:50:51 | 显示全部楼层
本帖最后由 ccarter 于 2016-3-23 03:57 编辑
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), ... 都可以满足条件。
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-11 03:17

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表