一道twitter的题 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

一道twitter的题

一道twitter的题# JobHunting - 待字闺中

h*02015-11-10 08:11

1 楼

Given two integers, a and b, determine the number of possible pairs of x,
y such that 1<=x<=a and 1<=y<=b and such that (x^1/3 + y^1/3)^3 is an
integer
大牛们，这道题应该怎么做？

I*c2015-11-10 08:11

2 楼

找出在1和a的三次方根之间所有的数的数目
找出在1和b的三次方根之间所有的数的数目
然后相乘
感觉很简单，是不是我想错了？

w*y2015-11-10 08:11

3 楼

【在 I******c 的大作中提到】

: 找出在1和a的三次方根之间所有的数的数目
: 找出在1和b的三次方根之间所有的数的数目
: 然后相乘
: 感觉很简单，是不是我想错了？

e*m2015-11-10 08:11

4 楼

x1 = (x1)^3 *m
y1= (y1)^3 *m

e*m2015-11-10 08:11

5 楼

x = (x1)^3 *m
y= (y1)^3 *m

h*02015-11-10 08:11

6 楼

我也觉得是这样，但是总感觉有隐藏东西在里面。可不可能存在x的三次方根是小数
，y的三次方根也是小数，但是他们之和为整数？

【在 I******c 的大作中提到】

: 找出在1和a的三次方根之间所有的数的数目
: 找出在1和b的三次方根之间所有的数的数目
: 然后相乘
: 感觉很简单，是不是我想错了？

I*c2015-11-10 08:11

7 楼

答案
https://www.quora.com/How-do-we-find-a-pair-of-integers-a-b-such-that-a-1-3-
+-b-1-3-3-is-an-integer

r*g2015-11-10 08:11

8 楼

这道题，及时知道你的链接内容也很难做啊，如何和好的搜索所有的pair呢，我没想到
好的办法。

3-

【在 I******c 的大作中提到】

: 答案
: https://www.quora.com/How-do-we-find-a-pair-of-integers-a-b-such-that-a-1-3-
: +-b-1-3-3-is-an-integer

I*c2015-11-10 08:11

9 楼

其实就是对x,y分别求它们的素数因数，然后放到hashmap里。
求素数因数可以看这个 http://www.geeksforgeeks.org/print-all-prime-factors-of-a-given-number/

g*y2015-11-10 08:11

10 楼

当然有可能，当x=y时。

x*92015-11-10 08:11

11 楼

这题大概这么做：
x = sum(xi ^ pi)
y = sum(yi ^ qi)
xi 和 yi 是 x, y 的质因数。
(x^1/3 + y^1/3)^3 => x^3 + y^3 + 3(x ^ 2/3)(y ^ 1/3) + 3(x ^ 1/3)(y ^ 2/3)
所以，如果想要式子为int，则“(x ^ 2/3)(y ^ 1/3) ”和“(x ^ 1/3)(y ^ 2/3)”
必须都为int。
此时，我们可以看出，对于xi == yi，当pi % 3== qi % 3时，两个子式才能为整数
于是，最终的解法是对于任意数K，进行质因数分解，然后再将列表进行
一次Hash。查询的时候拉出这个Hash链，再判断一下就行了。

c*m2015-11-10 08:11

12 楼

不太理解最后为什么要将放在hash table中。我的理解是最终得到两个数
组[p1, p2, ..., pn], [q1, q2, ...qn]。然后multiple_i { [0, pi]与[0, qi]各取
一数有多少组合满足pi%3==qi%3 }

【在 x*******9 的大作中提到】

: 这题大概这么做：
: x = sum(xi ^ pi)
: y = sum(yi ^ qi)
: xi 和 yi 是 x, y 的质因数。
: (x^1/3 + y^1/3)^3 => x^3 + y^3 + 3(x ^ 2/3)(y ^ 1/3) + 3(x ^ 1/3)(y ^ 2/3)
: 所以，如果想要式子为int，则“(x ^ 2/3)(y ^ 1/3) ”和“(x ^ 1/3)(y ^ 2/3)”
: 必须都为int。
: 此时，我们可以看出，对于xi == yi，当pi % 3== qi % 3时，两个子式才能为整数
: 于是，最终的解法是对于任意数K，进行质因数分解，然后再将列表进行
: 一次Hash。查询的时候拉出这个Hash链，再判断一下就行了。