i**********u
发帖数: 23 | 1 Hackerrank, 一小时两道。第二道10分钟，很简单，第一道怎么也想不到，样例都没全
过。提交后不到一天就收到拒信。
两个整数a，b满足0 < a <= m, 0 < b <= n，且(a^(1/3) + b^(1/3))^3也是整数
input：m,n
output: 满足以上关系的(a,b)的对数，比如m = 1, n = 8, 有两组 (1,1), (1,8) | p****n
发帖数: 17 | 2 a^(1/3)b^(1/3)(a^(1/3)+b^(1/3))
确保a^(1/3）, b^(1/3）都是整数 | y***x
发帖数: 148 | 3 就是找整数开立方吧
[在 iamxinyonghu () 的大作中提到：]
：Hackerrank, 一小时两道。第二道10分钟，很简单，第一道怎么也想不到，样例都没
全过。提交后不到一天就收到拒信。
：
：........... | t**c
发帖数: 480 | 4 a,b都是某数的三次方
这么一缩小范围，就基本没剩几个了
感觉比leetcode easy的题还简单啊 | i**********u
发帖数: 23 | 5 我没有试这个方法，因为2，16就可以满足，我觉得题面这么复杂，这么简单的答案还
能是T家么
【在 t**c 的大作中提到】
: a,b都是某数的三次方
: 这么一缩小范围，就基本没剩几个了
: 感觉比leetcode easy的题还简单啊
| a********m
发帖数: 15480 | 6 把a^(1/3)，b^(1/3)作为循环变量。
【在 i**********u 的大作中提到】
: Hackerrank, 一小时两道。第二道10分钟，很简单，第一道怎么也想不到，样例都没全
: 过。提交后不到一天就收到拒信。
: 两个整数a，b满足0 < a <= m, 0 < b <= n，且(a^(1/3) + b^(1/3))^3也是整数
: input：m,n
: output: 满足以上关系的(a,b)的对数，比如m = 1, n = 8, 有两组 (1,1), (1,8)
| i**********u
发帖数: 23 | 7 能详细点么，不是很明白，需要floating number参与计算么？
【在 a********m 的大作中提到】
: 把a^(1/3)，b^(1/3)作为循环变量。
| a********m
发帖数: 15480 | 8 完全不需要呀。
for (int i = 1; i * i * i <= m; ++i) {
for (int j = 1; j * j * j <= n; ++j) {
results.push(i * i * i, j * j * j);
}
}
【在 i**********u 的大作中提到】
: 能详细点么，不是很明白，需要floating number参与计算么？
| p**r
发帖数: 5853 | 9 个人感觉你被开立方给唬住了，
又不是让你人脑算，直接给啥公式写啥公式。
不过t也不行了，不去也好。
【在 i**********u 的大作中提到】
: Hackerrank, 一小时两道。第二道10分钟，很简单，第一道怎么也想不到，样例都没全
: 过。提交后不到一天就收到拒信。
: 两个整数a，b满足0 < a <= m, 0 < b <= n，且(a^(1/3) + b^(1/3))^3也是整数
: input：m,n
: output: 满足以上关系的(a,b)的对数，比如m = 1, n = 8, 有两组 (1,1), (1,8)
| i**********u
发帖数: 23 | 10 感觉不对啊，（2,16）这一对就漏了
【在 a********m 的大作中提到】
: 完全不需要呀。
: for (int i = 1; i * i * i <= m; ++i) {
: for (int j = 1; j * j * j <= n; ++j) {
: results.push(i * i * i, j * j * j);
: }
: }
| | | p**r
发帖数: 5853 | 11 你看下楼下虫子的解法，
一般面试的时候sqrt，开立方之类的都是转成n*n,n*n*...来做，
效率高。
【在 i**********u 的大作中提到】
: 能详细点么，不是很明白，需要floating number参与计算么？
| a********m
发帖数: 15480 | 12 哦。你说的对。
这样的话把刚才那个循环结果再过一遍。
for (k = 0; k < results.length; ++k) {
for (l = 0; l * results[l][0] < m && l * results[l][1] < n; ++l)
results2.push(l * results[l][0], l * results[l][1]);
for (l = 0; l * results[l][1] < m && l * results[l][0] < n; ++l)
results2.push(l * results[l][1], l * results[l][0]);
}
return results + results2;
【在 i**********u 的大作中提到】
: 感觉不对啊，（2,16）这一对就漏了
| i**********u
发帖数: 23 | 13 我的方法也差不多，把倍数的都算上，但是结果通不过。靠猜不严谨，总觉得还有别的
漏掉的。难道是个数学题？
【在 a********m 的大作中提到】
: 哦。你说的对。
: 这样的话把刚才那个循环结果再过一遍。
: for (k = 0; k < results.length; ++k) {
: for (l = 0; l * results[l][0] < m && l * results[l][1] < n; ++l)
: results2.push(l * results[l][0], l * results[l][1]);
: for (l = 0; l * results[l][1] < m && l * results[l][0] < n; ++l)
: results2.push(l * results[l][1], l * results[l][0]);
: }
: return results + results2;
| a********m
发帖数: 15480 | 14 应该不会的。估计是边界条件问题。三次方没有勾股定理。
看一下费马定理。
【在 i**********u 的大作中提到】
: 我的方法也差不多，把倍数的都算上，但是结果通不过。靠猜不严谨，总觉得还有别的
: 漏掉的。难道是个数学题？
| i**********u
发帖数: 23 | 15 恩，我也担心这个。我觉得这题如果没有严格证明，T家不应该拿出来吧。。。
【在 a********m 的大作中提到】
: 应该不会的。估计是边界条件问题。三次方没有勾股定理。
: 看一下费马定理。
| r****7
发帖数: 2282 | 16 直接遍历不就行了么。。。
【在 i**********u 的大作中提到】
: Hackerrank, 一小时两道。第二道10分钟，很简单，第一道怎么也想不到，样例都没全
: 过。提交后不到一天就收到拒信。
: 两个整数a，b满足0 < a <= m, 0 < b <= n，且(a^(1/3) + b^(1/3))^3也是整数
: input：m,n
: output: 满足以上关系的(a,b)的对数，比如m = 1, n = 8, 有两组 (1,1), (1,8)
| a********m
发帖数: 15480 | 17 费马定理20年前已经被证明了。呵呵。
【在 i**********u 的大作中提到】
: 恩，我也担心这个。我觉得这题如果没有严格证明，T家不应该拿出来吧。。。
| b**********5
发帖数: 7881 | 18 你怎么遍历 那个cube root？
double n1 = Math.cbrt(2.0);
double n2 = Math.cbrt(16.0);
double x = Math.pow(Math.cbrt(2.0) + Math.cbrt(16.0), 3.0);
那个最后的double x 不是integer。。。
【在 r****7 的大作中提到】
: 直接遍历不就行了么。。。
| b**********5
发帖数: 7881 | 19 你这个也不对啊， 还是得不到 （2，16）
比如 result是 [(1,1)，(1，8)]， 你下面这个循环怎么得到2，16的？
【在 a********m 的大作中提到】
: 哦。你说的对。
: 这样的话把刚才那个循环结果再过一遍。
: for (k = 0; k < results.length; ++k) {
: for (l = 0; l * results[l][0] < m && l * results[l][1] < n; ++l)
: results2.push(l * results[l][0], l * results[l][1]);
: for (l = 0; l * results[l][1] < m && l * results[l][0] < n; ++l)
: results2.push(l * results[l][1], l * results[l][0]);
: }
: return results + results2;
| b**********5
发帖数: 7881 | 20 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
我觉得这道题， 挺男的。 楼上几个说简单的， 拿code出来让我run一下， 你自己看
2，16 这个pair， or (3,27) pair 就知道了 | | | C*****n
发帖数: 1049 | 21 如果是easy难度给我的感觉就是：
先找出立方根是整数的那些数，如1,8,27,64等等，然后再乘以相同的倍数。
因为如果a、b可以写成a=kx, b=ky （k=2,3,4,...），那么：
(a^1/3 + b^1/3)^3= k(x^1/3 + y^1/3)
如果x、y是1、8、27、64这种数的话，那上面的式子也会是整数。
比如m=n=60，那么满足条件的对数是（假设a
(1,8),(2,16),(3,24),(4,32),(5,40),(6,48),(7,56)
(1,27),(2,54)
(8,27),(16,54)
剩下的问题就是证明如果a,b没有像k那样的公约数必然得不出(a^1/3 + b^1/3)^3为整
数。
【在 i**********u 的大作中提到】
: Hackerrank, 一小时两道。第二道10分钟，很简单，第一道怎么也想不到，样例都没全
: 过。提交后不到一天就收到拒信。
: 两个整数a，b满足0 < a <= m, 0 < b <= n，且(a^(1/3) + b^(1/3))^3也是整数
: input：m,n
: output: 满足以上关系的(a,b)的对数，比如m = 1, n = 8, 有两组 (1,1), (1,8)
| r*****s
发帖数: 1815 | 22 我觉得这题，挺简单的。
你说难，只要多想一步，就简单了。说白了不过是说，a，b可以分别写成x^3m和y^3n的
形式，其中m，n不能继续分解成如上形式或为1。
而经过简单替换，(m^2n)和(n^2m)都是整数的三次方，假设将m质因数分解，是q1q2q3.
..qc,n是p1p2p3...pd,则我们知道：m和n的分解中unique质因数一一对应，而且m和n的
分解中每种质因数的出现次数不是1就是2(否则和预处理步骤相悖)
具体考察一个质因数r，它在m里出现t次，在n里出现u次，我们要保证t*2+u和u*2+t都
可以被n整除，且t和u的值域都是1,2
否则就是两个cubic roots无理数相加是不是可能是有理数的问题，我手机实在不能打
了，这里有个链接：http://math.stackexchange.com/questions/437710/cube-roots-dont-sum-up-to-integer
由此可知，对于每一个质因数，要么同时t u都是1，要么同时都是2。
于是可知直觉正确，m和n相等。
于是可知，这两个数有x^3n和y^3n的形式
于是仍然是一道非常简单的题目
手机打字，很不方便。。
3-
【在 b**********5 的大作中提到】
: 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
: 我觉得这道题， 挺男的。 楼上几个说简单的， 拿code出来让我run一下， 你自己看
: 2，16 这个pair， or (3,27) pair 就知道了
| r*****s
发帖数: 1815 | 23 直觉是对的，你的头像怎么回事。。
【在 C*****n 的大作中提到】
: 如果是easy难度给我的感觉就是：
: 先找出立方根是整数的那些数，如1,8,27,64等等，然后再乘以相同的倍数。
: 因为如果a、b可以写成a=kx, b=ky （k=2,3,4,...），那么：
: (a^1/3 + b^1/3)^3= k(x^1/3 + y^1/3)
: 如果x、y是1、8、27、64这种数的话，那上面的式子也会是整数。
: 比如m=n=60，那么满足条件的对数是（假设a: (1,8),(2,16),(3,24),(4,32),(5,40),(6,48),(7,56)
: (1,27),(2,54)
: (8,27),(16,54)
: 剩下的问题就是证明如果a,b没有像k那样的公约数必然得不出(a^1/3 + b^1/3)^3为整
| l*******g
发帖数: 84 | 24 (1,1)
(2^0, 2^3),(2^1, 2^4)....
(3^0, 3^3),(3^1, 3^4)....
.
.
.
(x^n, x^(n+3))
{ x >=1 && n >= 0 } | r*******g
发帖数: 1335 | 25 这道题本版讨论过，需要质因数分解，分解之后也挺难，不好写程序。通俗的说，需要
由不同的质因数生成新的整数，满足范围要求。 | l*******g
发帖数: 84 | 26 list.Add( (1,1));
for( int i = 2 ;i <=n ; ++i )
for( int j = 0; Math.Pow( i, j + 3 ) <= m ; ++j )
list.Add( i, Math.Pow( i, j + 3) );
return list; | r*****s
发帖数: 1815 | 27 3, 24
【在 l*******g 的大作中提到】
: (1,1)
: (2^0, 2^3),(2^1, 2^4)....
: (3^0, 3^3),(3^1, 3^4)....
: .
: .
: .
: (x^n, x^(n+3))
: { x >=1 && n >= 0 }
| b**********5
发帖数: 7881 | 28 是啊， 这里一通人， 说话说了一大通， 没一个人写code的。 那些中文的technical
term， math term， 看的我都头疼。。。
【在 r*******g 的大作中提到】
: 这道题本版讨论过，需要质因数分解，分解之后也挺难，不好写程序。通俗的说，需要
: 由不同的质因数生成新的整数，满足范围要求。
| r*****s
发帖数: 1815 | 29 shabi.
x^3 ==> pow(x, 3)
for (int i = 0; i <= min(m,n); ++i) {
for (int x = 0; x^3*i <= m; ++x) {
for (int y = 0; y^3*i <= n; ++y) {
//insert x^3*i and y^3*i pair into a hash set:
set.insert(make_pair(x^3*i, x^3*i));
}
}
}
output(set)
there are lots of ways to dedup/optimize, but idea is clear and simple.
technical
【在 b**********5 的大作中提到】
: 是啊， 这里一通人， 说话说了一大通， 没一个人写code的。 那些中文的technical
: term， math term， 看的我都头疼。。。
| b**********5
发帖数: 7881 | 30 好像第一个iteration就不对啊， insert （0，0）。。。
【在 r*****s 的大作中提到】
: shabi.
: x^3 ==> pow(x, 3)
: for (int i = 0; i <= min(m,n); ++i) {
: for (int x = 0; x^3*i <= m; ++x) {
: for (int y = 0; y^3*i <= n; ++y) {
: //insert x^3*i and y^3*i pair into a hash set:
: set.insert(make_pair(x^3*i, x^3*i));
: }
: }
: }
| | | r*****s
发帖数: 1815 | 31 0, 0难道不符合 (a^1/3 + b^1/3) = 0?????
【在 b**********5 的大作中提到】
: 好像第一个iteration就不对啊， insert （0，0）。。。
| b**********5
发帖数: 7881 | 32 两个整数a，b满足0 < a <= m, 0 < b <= n
【在 r*****s 的大作中提到】
: 0, 0难道不符合 (a^1/3 + b^1/3) = 0?????
| r*****s
发帖数: 1815 | 33 那就去掉0呗，i,x,y都从1开始枚举。意思对了就行了，真是智障。你缺少思考的能力
，只会不断挑些细枝末节的毛病。
【在 b**********5 的大作中提到】
: 两个整数a，b满足0 < a <= m, 0 < b <= n
| b**********5
发帖数: 7881 | 34 tmd, 你去面试时候， 会对interviewer说这些话么？？！！
【在 r*****s 的大作中提到】
: 那就去掉0呗，i,x,y都从1开始枚举。意思对了就行了，真是智障。你缺少思考的能力
: ，只会不断挑些细枝末节的毛病。
| r*****s
发帖数: 1815 | 35 现在是你interview我吗？不是就他妈闭嘴，狗屁都想不出来我他妈义务给你提点一下
你他妈还有理了？
【在 b**********5 的大作中提到】
: tmd, 你去面试时候， 会对interviewer说这些话么？？！！
| r*****s
发帖数: 1815 | 36 i = 2
x = 1
y = 2
shabi
能力
【在 b**********5 的大作中提到】
: tmd, 你去面试时候， 会对interviewer说这些话么？？！！
| l******n
发帖数: 9344 | 37 效率低下的直接循环，应该不会漏
import math
m = 2
n = 16
for i in range(1,m+1):
for j in range(1,n+1):
a = i*1.0
b = j*1.0
if math.ceil(math.pow(a,1.0/3)*math.pow(b,1.0/3)*(math.pow(a,1.0/3)+
math.pow(b,1.0/3))) == math.floor(math.pow(a,1.0/3)*math.pow(b,1.0/3)*(math.
pow(a,1.0/3)+math.pow(b,1.0/3))):
print a,b
【在 i**********u 的大作中提到】
: Hackerrank, 一小时两道。第二道10分钟，很简单，第一道怎么也想不到，样例都没全
: 过。提交后不到一天就收到拒信。
: 两个整数a，b满足0 < a <= m, 0 < b <= n，且(a^(1/3) + b^(1/3))^3也是整数
: input：m,n
: output: 满足以上关系的(a,b)的对数，比如m = 1, n = 8, 有两组 (1,1), (1,8)
| f******b
发帖数: 1148 | 38 A b 是立方数
或者 a/b or b/a 是立方数
★ 发自iPhone App: ChineseWeb 1.0.6
【在 i**********u 的大作中提到】
: Hackerrank, 一小时两道。第二道10分钟，很简单，第一道怎么也想不到，样例都没全
: 过。提交后不到一天就收到拒信。
: 两个整数a，b满足0 < a <= m, 0 < b <= n，且(a^(1/3) + b^(1/3))^3也是整数
: input：m,n
: output: 满足以上关系的(a,b)的对数，比如m = 1, n = 8, 有两组 (1,1), (1,8)
| k*****e
发帖数: 93 | 39 大部分人都错了。
When a=b, it must be true. But most people forgot it.
beefcurtain5的是正解。
int pair_cubic(int m, int n)
{
set> s;
for(int i=1; i <= min(m,n); i++)
for(int a=1; a*a*a*i <= m; a++)
for(int b = 1; b*b*b*i <= n; b++)
s.insert(make_pair(a*a*a*i, b*b*b*i));
return s.size();
} | r*******y
发帖数: 270 | 40 那些说简单直接开立方的，这种做法是错误的。你道题需要质因数分解，不是一道简单
的题目。 | | | b********6
发帖数: 35437 | 41 把立方公式展开，就成了a + b + a^(2/3)b^(1/3) + a^(1/3)b^(2/3)
a和b肯定是整数，就是要考虑后面两项是整数的情况，严格的数学不知道怎么证
就是要求a=n^3 * k和b = m^3 * k的组合，一个一个试就行了
k = 1的时候，1，8，27，。。。
k = 2的时候，2，16，54.。。
k = 3的时候，3，24，81。。。
一直循环下去 | r*******g
发帖数: 1335 | 42 这道题牛肉姐不是已经贴了链接了吗，这不是一道简单的题，凡是不去求质因数的基本
都是错的吧。
通俗说，a=x1^n1*x2^n2*... b=x1^m1*x2^m2*....
其中x_i是质因数，n_i,m_i需要满足一定数学关系。所以先要求质因数，然后质因数还
要combination，我的想法是，先求出质因数，对x1把n1, n1+3, n1+6...这样的幂分成
一组，对x2，把n2, n2+3, n2+6....这样的分为一组，找出所有满足范围要求的组，这
一步不好写。
假设满足a范围要求的组有K个，每个里面有K_j个数，假设满足b范围要求的组有M个，
每个里面有M_j个。所以最后结果是K_j*M_j求和。这是因为，a的一个组，唯一对应b另
外的一个组。
所以这道题根本不简单，难点是怎么遍历combination，然后建立组。
如果不建立组，那对每个符合要求的a，你都要重新去遍历找b，开销是很大的。 | r*******g
发帖数: 1335 | 43 由于题目范围都是从0开始，所以感觉会有不少重复的，通俗的说，分组的时候，满足a
范围要求的数很多也满足b的范围要求。
a=x1^n1*x2^n2*.最开始n1,n2...都是0，但是怎么逐渐增大n_i呢？ | b********6
发帖数: 35437 | 44 谁来测一下我这个程序？
vector > triple( int n )
{
vector > ans;
if( n < 1 )
return ans;
int i = 1;
while( i <= n )
{
ans.push_back(make_pair( i , i));
for( int j = 2; i*j*j*j <= n; j++ )
{
ans.push_back(make_pair( i , i*j*j*j));
ans.push_back(make_pair( i*j*j*j , i));
}
i++;
}
return ans;
} | l***i
发帖数: 1309 | 45 Here is an idea and a proof sketch.
Solution: (c*a, c*b) for cubic numbers a and b and integer c >= 1. It is
easy to see those are solutions, but takes a proof to show that they are the
only solutions.
Observation: if (a,b) is a solution, then (k*a, k*b) is also a solution, for
integer k >= 1.
Claim: If (a, b) is a solution, then both a and b must be cubic numbers.
Now let's prove that claim. W.l.o.g. we may assume gcd(a,b) = 1, and we may
also assume that a is not a cubic number. Let p be a prime factor of a. We
know that b does not divide p.
Let u = a^1/3 and v = b^1/3, also let a = p*q
(u + v)^3 = a + b + u^2*v + u*v^2
Notice that u^2*v * u*v^2 = u^3 * v^3 = a * b is an integer, so u^2*v is an
integer iff u*v^2 is an integer.
u^2*v = p^2/3 * q^2/3 * b^1/3
This cannot be an integer because p is a prime and u^2*v must divide p if u^
2*v is an integer. (* This step is hand wavy and some number theory expert
please tell me what theorem needed here. *)
For the same reason u*v^2 is not an integer.
Q.E.D. | j**********3
发帖数: 3211 | | l******8
发帖数: 1691 | 47 赞！
q1q2q3.
【在 r*****s 的大作中提到】
: 我觉得这题，挺简单的。
: 你说难，只要多想一步，就简单了。说白了不过是说，a，b可以分别写成x^3m和y^3n的
: 形式，其中m，n不能继续分解成如上形式或为1。
: 而经过简单替换，(m^2n)和(n^2m)都是整数的三次方，假设将m质因数分解，是q1q2q3.
: ..qc,n是p1p2p3...pd,则我们知道：m和n的分解中unique质因数一一对应，而且m和n的
: 分解中每种质因数的出现次数不是1就是2(否则和预处理步骤相悖)
: 具体考察一个质因数r，它在m里出现t次，在n里出现u次，我们要保证t*2+u和u*2+t都
: 可以被n整除，且t和u的值域都是1,2
: 否则就是两个cubic roots无理数相加是不是可能是有理数的问题，我手机实在不能打
: 了，这里有个链接：http://math.stackexchange.com/questions/437710/cube-roots-dont-sum-up-to-integer
| N*D
发帖数: 3641 | 48 (a+b)^3展开，其实就是找a和b可以开三次方的，以及a^2*b和a*b^2可以开三次方的就
可以了，对吧？ | s***a
发帖数: 82 | 49 呵呵， 确实。
这里好多人如果我面试， 肯定不让过， 不是因为答的不对， 而是思维心态很不open。
【在 r*******y 的大作中提到】
: 那些说简单直接开立方的，这种做法是错误的。你道题需要质因数分解，不是一道简单
: 的题目。
| l******n
发帖数: 9344 | 50 面试的时候时间那么紧，当然先从最简单直接明了的方式做起，有时间再改进。如果你
希望应试者用特定的思路做，你需要明确的提示
感觉老中面试官对中国人就是这种心态，都以为自己是bar raiser,吹毛求疵.如果来面
试的老美，估计就是另外的说法了。多学学烙印，不是光被整了之后嘴上的发发牢骚
open。
【在 s***a 的大作中提到】
: 呵呵， 确实。
: 这里好多人如果我面试， 肯定不让过， 不是因为答的不对， 而是思维心态很不open。
| | | m***b
发帖数: 30 | 51 for (k = 1,2,3,4.....)
for (j = k, k+1, k+2, ........)
for (p = 1, 2, 3, .........)
a = p * k^3 <=m
b = p * j^3 <=n | n*****g
发帖数: 365 | 52 这个题的表达式展开后：
(a^(1/3)+b^(1/3))^3 = 3(ab)^(1/3)(a^(1/3)+b^(1/3)) + a +b
所以关键是 前半部分是整数：(ab)^(1/3)(a^(1/3)+b^(1/3))
加入 b>a, and b=a^m,上式变为：
a^(m+2/3)(1+a^m)
为保证整数，m可取1,4,7，，
所以，b=a^1 (b==a) , b=a^4, b=a^7,,,
这样可以保证把3,27 和 2,16 包括进去。程序需要遍历 O(M*N)
感觉初中奥赛题目呀啊，年纪大了力不从心 | r*****s
发帖数: 1815 | 53 错了。2, 54
【在 n*****g 的大作中提到】
: 这个题的表达式展开后：
: (a^(1/3)+b^(1/3))^3 = 3(ab)^(1/3)(a^(1/3)+b^(1/3)) + a +b
: 所以关键是 前半部分是整数：(ab)^(1/3)(a^(1/3)+b^(1/3))
: 加入 b>a, and b=a^m,上式变为：
: a^(m+2/3)(1+a^m)
: 为保证整数，m可取1,4,7，，
: 所以，b=a^1 (b==a) , b=a^4, b=a^7,,,
: 这样可以保证把3,27 和 2,16 包括进去。程序需要遍历 O(M*N)
: 感觉初中奥赛题目呀啊，年纪大了力不从心
|
|
