挑战C版所有人，1000！ - C语言论坛

编程论坛 → 开发语言 → 『 C语言论坛』 → 挑战C版所有人，1000！

标题：挑战C版所有人，1000！

只看楼主

童生

等　级：侠之大者
威　望：8
帖　子：205
专家分：455
注　册：2018-3-7

第 21 楼

得分:0

先谢谢置顶，这个论坛与我有一些缘源,所以我放胆在此挑战!

[此贴子已经被作者于2018-6-1 23:01编辑过]

2018-06-01 22:59

九转星河

来　自：长长久久
等　级：贵宾
威　望：52
帖　子：5023
专家分：14003
注　册：2016-10-22

第 22 楼

得分:0

以下是引用童生在2018-6-1 22:50:42的发言：

希望您(注意是您)参与,不过先过了https://bbs.bccn.net/viewthread.php?tid=32009&highlight=%2Bkai这一贴，再贴代码

我就知道没有那么简单,毕竟我能力有限还是观望吧

记得我还看到有个计算10亿以内的素数个数的算法还有个快速求平方算法,我知道这个也肯定存在某些特别高效的算法的,嗯或者说不定楼主那个算法是最快的那种了(个人猜想最快算法是斯特林公式加傅里叶变换加快速幂综合求解),但这样算法复杂度确实比较高,我……还是观望吧
(别说我有那个能耐,我知道自己那些自己能弄出来那些自己弄不出来的,这个……我还是路过好了)

[此贴子已经被作者于2018-6-1 23:06编辑过]

[code]/*~个性签名:bug是什么意思?bug是看上去没有可能的东西实际上是有可能做到的就是这样~2018-08-08更~*/[/code]

2018-06-01 23:04

童生

等　级：侠之大者
威　望：8
帖　子：205
专家分：455
注　册：2018-3-7

第 23 楼

得分:0

1000!只不过是个虚拟设定数,你要10000!，100000！.....都可以，或者其他只要您提出来

2018-06-01 23:05

童生

等　级：侠之大者
威　望：8
帖　子：205
专家分：455
注　册：2018-3-7

第 24 楼

得分:0

以下是引用九转星河在2018-6-1 23:04:37的发言：

我就知道没有那么简单,毕竟我能力有限还是观望吧

记得我还看到有个计算10亿以内的素数算法还有个快速求平方算法,我知道这个也肯定存在某些特别高效的算法的,嗯或者说不定楼主那个算法是最快的那种了(个人猜想最快算法是斯特林公式加傅里叶变换加快速幂综合求解),但这样算法复杂度确实比较高,我……还是观望吧
(别说我有那个能耐,我知道自己那些自己能弄出来那些自己弄不出来的,这个……我还是路过好了)

你可以的，一个人不在于当下知道什么，而在于自身习性或者说品格或者本性或....什么我也没有准确词来表述

2018-06-01 23:09

童生

等　级：侠之大者
威　望：8
帖　子：205
专家分：455
注　册：2018-3-7

第 25 楼

得分:0

不好意思啊，喝了酒发此贴，但是我承诺3年之内我尊守此所有约定，包括本ID马甲!

2018-06-01 23:14

自学的数学

等　级：贵宾
威　望：46
帖　子：967
专家分：4146
注　册：2017-11-15

第 26 楼

得分:0

https://bbs.bccn.net/viewthread.php?tid=32009&highlight=%2Bkai
这都是10多年前的帖子了。当时最快速度好像是7.9秒。不知现在。。。。。。

2018-06-01 23:17

九转星河

来　自：长长久久
等　级：贵宾
威　望：52
帖　子：5023
专家分：14003
注　册：2016-10-22

第 27 楼

得分:0

回复 24楼童生

我就说一种方法吧不过实现代码实现就是另一回事了,但起码先知道方法~

不开buff也就是不用斯特林公式来说,可以这样(实话说,那个公式是一个bug级别的存在,但不排除一些专业的比赛上要用到)
先把1000以内的数进行分解质因式~

然后可以得到1000!=k1^n1*k2^n2*k3^n3……*ki^ni

问题就是怎么用快速幂对大数进行次方运算,想了想,无论怎么计算,到最后怎么也要在大数乘法运算上进行优化吧,所以个人感觉傅里叶快速变换还是要用到的

[此贴子已经被作者于2018-6-1 23:22编辑过]

[code]/*~个性签名:bug是什么意思?bug是看上去没有可能的东西实际上是有可能做到的就是这样~2018-08-08更~*/[/code]

2018-06-01 23:19

童生

等　级：侠之大者
威　望：8
帖　子：205
专家分：455
注　册：2018-3-7

第 28 楼

得分:0

以下是引用自学的数学在2018-6-1 23:17:57的发言：

https://bbs.bccn.net/viewthread.php?tid=32009&highlight=%2Bkai
这都是10多年前的帖子了。当时最快速度好像是7.9秒。不知现在。。。。。。

你先用他们的代码在你的电脑上试试先再发表意见不行么？

2018-06-01 23:19

童生

等　级：侠之大者
威　望：8
帖　子：205
专家分：455
注　册：2018-3-7

第 29 楼

得分:0

以下是引用九转星河在2018-6-1 23:19:14的发言：

我就说一种方法吧不过实现代码实现就是另一回事了,但起码先知道方法~

不开buff也就是不用斯特林公式来说,可以这样(实话说,那个公式是一个bug级别的存在,但不排除一些专业的比赛上要用到)
先把1000以内的数进行分解质因式~

然后可以得到1000!=k1^n1*k2^n2*k3^n3

问题就是怎么用快速幂对大数进行次方运算,想了想,无论怎么计算,到最后怎么也要在大数乘法运算上进行优化吧,所以个人感觉傅里叶快速变换还是要用到的

精确计算这是前题，不管您用什么方法

2018-06-01 23:21

童生

等　级：侠之大者
威　望：8
帖　子：205
专家分：455
注　册：2018-3-7

第 30 楼

得分:0

以下是引用九转星河在2018-6-1 23:19:14的发言：

我就说一种方法吧不过实现代码实现就是另一回事了,但起码先知道方法~

不开buff也就是不用斯特林公式来说,可以这样(实话说,那个公式是一个bug级别的存在,但不排除一些专业的比赛上要用到)
先把1000以内的数进行分解质因式~

然后可以得到1000!=k1^n1*k2^n2*k3^n3……*kN*n^N

问题就是怎么用快速幂对大数进行次方运算,想了想,无论怎么计算,到最后怎么也要在大数乘法运算上进行优化吧,所以个人感觉傅里叶快速变换还是要用到的

与您讨论1000!算法,不行，至少放到1000000!

2018-06-01 23:23

参与讨论请移步原网站贴子：https://bbs.bccn.net/thread-487524-1-1.html