数论方面算法问题,如何快速判断n!+1为完全平方数的n或者说快速得知一段区间内满足这种性质的n的个数比如4!+1=5*5 +1=11*11 +1=71*71等等拒绝一切只用暴力枚举的思想做的，要枚举也得有极强剪
来源：学生作业帮助网 编辑：六六作业网 时间：2024/12/18 16:50:29
数论方面算法问题,如何快速判断n!+1为完全平方数的n或者说快速得知一段区间内满足这种性质的n的个数比如4!+1=5*5 +1=11*11 +1=71*71等等拒绝一切只用暴力枚举的思想做的，要枚举也得有极强剪
数论方面算法问题,如何快速判断n!+1为完全平方数的n
或者说快速得知一段区间内满足这种性质的n的个数
比如4!+1=5*5 +1=11*11 +1=71*71等等
拒绝一切只用暴力枚举的思想做的，要枚举也得有极强剪枝才行
欢迎一切数论思想、结论或方法！
数论方面算法问题,如何快速判断n!+1为完全平方数的n或者说快速得知一段区间内满足这种性质的n的个数比如4!+1=5*5 +1=11*11 +1=71*71等等拒绝一切只用暴力枚举的思想做的，要枚举也得有极强剪
你先要讲清楚你所说的区间大致是从几到几的区间,这直接影响到什么样子的算法是可以接受的.不要很笼统地说区间越大越好,算法越快越好.
在n比较小的时候当然是枚举最方便,即使是需要考虑大数运算的复杂程度.
当n比较大之后n!的末尾是连续的k个0,k可以通过1:n中5的因子出现次数来得到,这样如果n!+1是平方数的话,其平方根必定是p*10^k+1或者p*10^k-1的形式,这样相当于验证n!=A(A+2),可以先用实数运算算出ln(n!)=ln((n-1)!)+ln(n)（这步的舍入误差其实是很小的）,仅当估计得到的A或者A+2非常接近p*10^k的形式时才进一步验证.
当n大到一定程度的时候,A^2>>2A,只需要验证ln(n!)=2ln(A),当A非常接近p*10^k时才进一步验证.
再说一下所谓的“进一步验证”,首先是利用浮点舍入误差分析计算出误差界来估计所谓的“非常接近”,然后对A和A+2进行质因子分解(也要用大数计算).
写一些个人的想法，谈不上解答，大家一起讨论讨论。
*****************************************************
（1）首先分析n!：
当n>=5时，这个数的末位数字必然是0，这个是很显然，因为n!里面有因数2和5，乘起来必然末位是0.
那么n!+1末位必然是1.
如果这个数是完全平方数，n!+1=a^2,那么a的...
全部展开
写一些个人的想法，谈不上解答，大家一起讨论讨论。
*****************************************************
（1）首先分析n!：
当n>=5时，这个数的末位数字必然是0，这个是很显然，因为n!里面有因数2和5，乘起来必然末位是0.
那么n!+1末位必然是1.
如果这个数是完全平方数，n!+1=a^2,那么a的末位数字不是1就是9.
（2）其次看n!的变化规律：
n!到(n+1)!就要扩大n+1倍！当n很大时，这种增长是相当剧烈的。如果我们把1!,2!,3!,...标在数轴上的话，我们会发现他们越来越稀疏。
比如，从10!到11！，这是一个很大的区间了（都已经差一个数量级了），然而这个区间理要考察的数只有两个。所以我觉得题中“得知一段区间内满足这种性质的n的个数”其实不想想象中的那样多，很有可能好大一个区间里只有一个数是n!+1，甚至一个都没有。
（3）结合上面两部分析：
好大的区间内只有少数几个数是n!+1，在这其中有可能是完全平方数的话，只有是“1^2”或者“9^2”这两种类型。那么我觉得只要用试验法就行了。找出有可能是答案的几个数试一下，如果都不是，那就能确定这段区间里没有这样的数.
**************************************************************
本人是学工科的，对《数论》《近世代数》只是略知一二，暂时无法想出纯数学解法，还请谅解。
收起