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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 找出在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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 找出在1和a的三次方根之间所有的数的数目 : 找出在1和b的三次方根之间所有的数的数目 : 然后相乘 : 感觉很简单,是不是我想错了?
|
I******c 发帖数: 163 | |
r*******g 发帖数: 1335 | 8 这道题,及时知道你的链接内容也很难做啊,如何和好的搜索所有的pair呢,我没想到
好的办法。
3-
【在 I******c 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 答案 : 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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 这题大概这么做: : 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链,再判断一下就行了。
|