h*******0
发帖数: 270 | 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******c
发帖数: 163 | 2 找出在1和a的三次方根之间所有的数的数目
找出在1和b的三次方根之间所有的数的数目
然后相乘
感觉很简单，是不是我想错了？ |
w*****y
发帖数: 4 | 3
【在 I******c 的大作中提到】
: 找出在1和a的三次方根之间所有的数的数目
: 找出在1和b的三次方根之间所有的数的数目
: 然后相乘
: 感觉很简单，是不是我想错了？
|
e****m
发帖数: 484 | 4 x1 = (x1)^3 *m
y1= (y1)^3 *m |
e****m
发帖数: 484 | 5 x = (x1)^3 *m
y= (y1)^3 *m |
h*******0
发帖数: 270 | 6 我也觉得是这样，但是总感觉有隐藏东西在里面。 可不可能存在x的三次方根是小数
，y的三次方根也是小数，但是他们之和为整数？
【在 I******c 的大作中提到】
: 找出在1和a的三次方根之间所有的数的数目
: 找出在1和b的三次方根之间所有的数的数目
: 然后相乘
: 感觉很简单，是不是我想错了？
|
I******c
发帖数: 163 | |
r*******g
发帖数: 1335 | 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******c
发帖数: 163 | |
g*y
发帖数: 30 | |
x*******9
发帖数: 138 | 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*****m
发帖数: 271 | 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链，再判断一下就行了。
|
