- 主题:求解奥数题
从1至100中最多取出多少个数，才能够确保其中任意两个数的最小公倍数和最大公约数的商不是完全平方数？
2014年ycb大师赛六年级的题目，答案是61.求解题思路
--
FROM 123.112.70.*
想想这两个数的乘积是什么样的数
--
FROM 120.244.141.*
最小公倍数是俩数的积除以最大公约数吧，所以就是俩数的积除以最大公约数平方，如果商还是完全平方数，那俩数的积得是完全平方数吧，也就是说，你把俩数的积是完全平方数的除去吧
【 在 mistery 的大作中提到: 】
: 从1至100中最多取出多少个数，才能够确保其中任意两个数的最小公倍数和最大公约数的商不是完全平方数？
: 2014年ycb大师赛六年级的题目，答案是61.求解题思路
--
FROM 219.236.120.40
这样的数有23个，去除了还有76个，还是不对
【 在 defeatyou 的大作中提到: 】
: 最小公倍数是俩数的积除以最大公约数吧，所以就是俩数的积除以最大公约数平方，如果商还是完全平方数，那俩数的积得是完全平方数吧，也就是说，你把俩数的积是完全平方数的除去吧
--
FROM 123.112.70.*
两数字P，Q，gcd(P,Q) = m, 表示P=am, Q=bm，a,b互质。那lcm/gcd = ab，所以这题要找的就是a、b不能都是perfect square的数。
考虑完全平方数及其倍数，相同倍数的完全平方数只能取一个，例如，3*1^2，3*2^2，3*3^2...3*5^2，这里面只能取一个，否则此两数除以lcm后都是完全平方数了。倍数最大只能是23，即23*4。然后还要除掉4，8，9，12，16，18，20等还有完全平方数为因子的，因为这些书已包含。这样一共是55个数中取了16个。加上剩下的45正好61。
【 在 mistery 的大作中提到: 】
: 这样的数有23个，去除了还有76个，还是不对
--
FROM 114.245.81.*
明白了，谢谢！
【 在 zidan 的大作中提到: 】
: 两数字P，Q，gcd(P,Q) = m, 表示P=am, Q=bm，a,b互质。那lcm/gcd = ab，所以这题要找的就是a、b不能都是perfect square的数。
: 考虑完全平方数及其倍数，相同倍数的完全平方数只能取一个，例如，3*1^2，3*2^2，3*3^2...3*5^2，这里面只能取一个，否则此两数除以lcm后都是完全平方数了。倍数最大只能是23，即23*4。然后还要除掉4，8，9，12，16，18，20等还有完全平方数为因子的，因为这些书已包含。这样一共是55个数中取了16个。加上剩下的45正好61。
:
--
FROM 123.112.70.*