100位平方数和立方数

kofeffect

呵呵，无心人是想确认我在8#说的，然后就顺便用Haskell来show一下而已

无心人

是的 不叫show 就让haskell和PARI一样的待遇吧

kofeffect

楼上说的PARI是否这个？ PARI/GP is a widely used computer algebra system designed for fast computations in number theory (factorizations, algebraic number theory, elliptic curves...), but also contains a large number of other useful functions to compute with mathematical entities such as matrices, polynomials, power series, algebraic numbers etc., and a lot of transcendental functions. PARI is also available as a C library to allow for faster computations. http://pari.math.u-bordeaux.fr/

无心人

是的 数学几大工具之一

northwolves

试了试pari，确实很爽

KeyTo9_Fans

这个问题其实不难，因为只要求求最大和最小的。 我估算了一下，每个在范围的平方数或立方数，大概$1/{500,000}$的概率符合条件，所以穷举不难 mathe 发表于 2009-1-13 15:33

你的概率估算不正确，把人家给误导了。 要找最小的平方数，那么要从这个数的 1000000000011111111122222222223333333333444444444455555555556666666666777777777788888888889999999999 平方根开始枚举。 你要想想，这个数的平方根有50位，设为$x$，取上整。 我们要从$x$开始，依次检查 $x^2$、$(x+1)^2$、$(x+2)^2$、$(x+3)^2$、…… 是否符合条件。 可是即使检查了10亿个完全平方数， 这些完全平方数的前40位仍旧雷打不动，动的只是后60位。 也就是说，前40位是 1000000000011111111122222222223333333333...... 恒定不变。 于是前40位把0、1、2、3的配额全花光了， 导致后面60位全都不允许出现0、1、2、3。 且不论4~9的数字个数问题，就光凭上面那条限制，就已经使得符合条件的概率不大于 $0.6^60=4.888e-14$ 了。 也就是说，我们至少要往后检查20万亿个完全平方数，才能期望有1个完全平方数符合条件。 求最大的也是一样囧况。 哪有你说的那么轻松

056254628

mathe就经常犯这种错误。我这个外来人就见到他很多次。

056254628

我觉得这道题可以这么做： 设所求的最小平方数数为n^2,那么 sqrt(10)*10^49

liangbch

必须找出更多的约束条件，否则穷举不可行，期望mathe找出更多的约束条件。

liangbch

如果单纯采取构造法，包含10个不同的数字，每个数字出现10次的排列数是 $(100!)/((10!)^10)=2.35xx10^92$,显然计算机无法穷举。 我们考察一下下面的方法的复杂度。 预备知识： 若x是一个n位数，则$x^2$是一个2n位数或者2n-1位数，2n-1位数看做首位为0的2n位数。在x很大的情况下，$x^2$和$(x+1)^2$的前n位数不相同概率接近100%，当x比较小的时候，这个概率稍低。2n位首位为0的平方数且前n位数相同者，最多只有5个，2n位首位不为0的平方数且前n位数相同者最多只有2个。 对于此题，可按照下列算法去搜索。 1. 构造一个100位数p，使得在前50个数字中，每个数字最多出现10次，后50位数字为0，求p的平方根并向上取整得x. 2. 若$x^2$满足条件，即包含0到9各10次，程序结束。若$x^2$前50个数字与p的前50个数字不同，转4 3. x++,并 转2 4. 构造另一个100位数字p,求其平方根并向上取整得x，并转2 复杂度分析，50个数字的所有排列为$10^50$，若加上限制条件，前50位数中，每个数字最多出现10次，则实际排列数可大大降低，我不知道这个数是多少，请高手给出答案。假设这个排列数c比较小，则枚举所有符合条件的数是可行的,实际运算次数正比于c。