回复 10# gxqcn 的帖子
呵呵，无心人是想确认我在8#说的，然后就顺便用Haskell来show一下而已:) 是的不叫show
就让haskell和PARI一样的待遇吧 楼上说的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/ 是的
数学几大工具之一 试了试pari，确实很爽 这个问题其实不难，因为只要求求最大和最小的。
我估算了一下，每个在范围的平方数或立方数，大概$1/{500,000}$的概率符合条件，所以穷举不难
mathe 发表于 2009-1-13 15:33 http://bbs.emath.ac.cn/images/common/back.gif
你的概率估算不正确，把人家给误导了。:M:
要找最小的平方数，那么要从这个数的
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个完全平方数符合条件。
求最大的也是一样囧况。
哪有你说的那么轻松:'( mathe就经常犯这种错误。我这个外来人就见到他很多次。 我觉得这道题可以这么做：
设所求的最小平方数数为n^2,那么sqrt(10)*10^49<n<10^50
且 n为3的倍数。可以从最小的n开始穷举，每次检查n^2是不是符合要求，若符合由10个0-9构成就大功告成。
求最大的平方数，则从最大的n开始往下搜索。
-------------------------------------------
而求立方数，搜索的范围更小。 必须找出更多的约束条件，否则穷举不可行，期望mathe找出更多的约束条件。 本帖最后由 liangbch 于 2010-1-21 16:02 编辑
如果单纯采取构造法，包含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。