要回国了,写个简单的总结吧。

一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
码农求职神器Triplebyte:
不用海投
内推多家公司面试
坐标湾区
Games Startup
招聘游戏开发工程师
游戏初创公司招聘工程师、UIUX Designer和游戏策划
把贵司招聘信息放这里
查看: 1996|回复: 5
收起左侧

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

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

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

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

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

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


上一篇:求刷题小伙伴!! LZ写c++ 互相监督 现在就可开始 汉子妹子们都来吧
下一篇:Groupon面试题
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

使用道具 举报

全球28万学生4.7分推荐
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), ... 都可以满足条件。
回复 支持 反对

使用道具 举报

本版积分规则

提醒:发帖可以选择内容隐藏,部分板块支持匿名发帖。请认真读完以下全部说明:

■隐藏内容方法: [hide=200]你想要隐藏的内容比如面经[/hide]
■意思是:用户积分低于200则看不到被隐藏的内容
■可以自行设置积分值,不建议太高(200以上太多人看不到),也不建议太低(那就没必要隐藏了)
■建议只隐藏关键内容,比如具体的面试题目、涉及隐私的信息,大部分内容没必要隐藏。
■微信/QQ/电子邮件等,为防止将来被骚扰甚至人肉,以论坛私信方式发给对方最安全。
■匿名发帖的板块和方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

关闭

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

手机版|小黑屋|一亩三分地论坛声明

custom counter

GMT+8, 2018-5-27 09:43

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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