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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : a,b都是某数的三次方 : 这么一缩小范围,就基本没剩几个了 : 感觉比leetcode easy的题还简单啊
| a********m 发帖数: 15480 | 6 把a^(1/3),b^(1/3)作为循环变量。
【在 i**********u 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 把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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 能详细点么,不是很明白,需要floating number参与计算么?
| p**r 发帖数: 5853 | 9 个人感觉你被开立方给唬住了,
又不是让你人脑算,直接给啥公式写啥公式。
不过t也不行了,不去也好。
【在 i**********u 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 完全不需要呀。 : 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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 能详细点么,不是很明白,需要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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 感觉不对啊,(2,16)这一对就漏了
| i**********u 发帖数: 23 | 13 我的方法也差不多,把倍数的都算上,但是结果通不过。靠猜不严谨,总觉得还有别的
漏掉的。难道是个数学题?
【在 a********m 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 哦。你说的对。 : 这样的话把刚才那个循环结果再过一遍。 : 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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 我的方法也差不多,把倍数的都算上,但是结果通不过。靠猜不严谨,总觉得还有别的 : 漏掉的。难道是个数学题?
| i**********u 发帖数: 23 | 15 恩,我也担心这个。我觉得这题如果没有严格证明,T家不应该拿出来吧。。。
【在 a********m 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 应该不会的。估计是边界条件问题。三次方没有勾股定理。 : 看一下费马定理。
| r****7 发帖数: 2282 | 16 直接遍历不就行了么。。。
【在 i**********u 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 恩,我也担心这个。我觉得这题如果没有严格证明,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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 直接遍历不就行了么。。。
| b**********5 发帖数: 7881 | 19 你这个也不对啊, 还是得不到 (2,16)
比如 result是 [(1,1),(1,8)], 你下面这个循环怎么得到2,16的?
【在 a********m 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 哦。你说的对。 : 这样的话把刚才那个循环结果再过一遍。 : 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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 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 的大作中提到】![](/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 : 我觉得这道题, 挺男的。 楼上几个说简单的, 拿code出来让我run一下, 你自己看 : 2,16 这个pair, or (3,27) pair 就知道了
| r*****s 发帖数: 1815 | 23 直觉是对的,你的头像怎么回事。。
【在 C*****n 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 如果是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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : (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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 这道题本版讨论过,需要质因数分解,分解之后也挺难,不好写程序。通俗的说,需要 : 由不同的质因数生成新的整数,满足范围要求。
| 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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 是啊, 这里一通人, 说话说了一大通, 没一个人写code的。 那些中文的technical : term, math term, 看的我都头疼。。。
| b**********5 发帖数: 7881 | 30 好像第一个iteration就不对啊, insert (0,0)。。。
【在 r*****s 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 好像第一个iteration就不对啊, insert (0,0)。。。
| b**********5 发帖数: 7881 | 32 两个整数a,b满足0 < a <= m, 0 < b <= n
【在 r*****s 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 0, 0难道不符合 (a^1/3 + b^1/3) = 0?????
| r*****s 发帖数: 1815 | 33 那就去掉0呗,i,x,y都从1开始枚举。意思对了就行了,真是智障。你缺少思考的能力
,只会不断挑些细枝末节的毛病。
【在 b**********5 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 两个整数a,b满足0 < a <= m, 0 < b <= n
| b**********5 发帖数: 7881 | 34 tmd, 你去面试时候, 会对interviewer说这些话么??!!
【在 r*****s 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 那就去掉0呗,i,x,y都从1开始枚举。意思对了就行了,真是智障。你缺少思考的能力 : ,只会不断挑些细枝末节的毛病。
| r*****s 发帖数: 1815 | 35 现在是你interview我吗?不是就他妈闭嘴,狗屁都想不出来我他妈义务给你提点一下
你他妈还有理了?
【在 b**********5 的大作中提到】![](/moin_static193/solenoid/img/up.png) : tmd, 你去面试时候, 会对interviewer说这些话么??!!
| r*****s 发帖数: 1815 | 36 i = 2
x = 1
y = 2
shabi
能力
【在 b**********5 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 我觉得这题,挺简单的。 : 你说难,只要多想一步,就简单了。说白了不过是说,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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 那些说简单直接开立方的,这种做法是错误的。你道题需要质因数分解,不是一道简单 : 的题目。
| l******n 发帖数: 9344 | 50 面试的时候时间那么紧,当然先从最简单直接明了的方式做起,有时间再改进。如果你
希望应试者用特定的思路做,你需要明确的提示
感觉老中面试官对中国人就是这种心态,都以为自己是bar raiser,吹毛求疵.如果来面
试的老美,估计就是另外的说法了。多学学烙印,不是光被整了之后嘴上的发发牢骚
open。
【在 s***a 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 呵呵, 确实。 : 这里好多人如果我面试, 肯定不让过, 不是因为答的不对, 而是思维心态很不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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 这个题的表达式展开后: : (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) : 感觉初中奥赛题目呀啊,年纪大了力不从心
|
|