主题：[讨论]输入N，输出N！的最后一位非0的数字
Templar9d
[专家分：2110] 发布于 2007-05-20 09:03:00
此题唤起我童年的记忆...
当年我找规律....进行优化...最终没给出好结果。
我当时处理方式是利用C的位运算进行末几位的高精度计算，但是时间复杂度为O(N)，当N很大时就没戏了。
昨天重新考虑了一下，得出一个可以证明的解法。时间复杂度为O(log(2, N)*log(5, N))，空间复杂度相同（递归）。
思路如下：
从1到N中：所有奇数末尾的3、5、7、9个数后抛弃。所有偶数各分离掉一个2，就得到一个新的自然数列，1到N/2。
找到了一个基本思想。可以统计出所有数的因子中，2，5的个数，还有3、5、7结尾的因子的个数。下面进一步完善。
显然1到N中，每10个数就有3、5、7、9各一个。至于最后的不到10各的零头也很容易可以根据零头的大小推断是否还有3、5、7、9。这样就是把N除以10的商和余数分离出来，进行4个判断就可以得到准确的3、5、7、9的个数。
2的个数就更简单了，直接为N/2.。也就是说整个过程不用从1到N依次分析，而是只要分析N这个数。
然后就考虑另一个情况：末尾是5的数只被计为一个5就被丢弃是不正确的，应该将其中的5分离出来然后再处理它的末位。于是我们每次做完以上操作后要进行另外一个递归，把N个数中5的倍数之外的数丢弃，然后各提取一个因子5，得到一个新序列1到N/5。然后统计其中的5、3、7、9的个数。方法同上，还是只分析N。
这样把2、5和3、7、9结尾因数的个数统计出来，5的个数抵消掉一部分2，最后就相当于若干2、3、7、9的相乘。我们找到的规律是：
个数 1 2 3 4 5
2 2 4 8 6 2
3 3 9 7 1 3
7 7 9 3 1 7
9 9 1 9 1 9
就是说这些它们幂的末尾数字都以4为循环周期，于是我们没必要用精度很高的空间去记录它们准确的个数，只要记录个数除以4的余数。
以上过程很难描述清楚，我还是建议大家结合自己的思考。
我自己的程序是C＋＋的，有兴趣的可以参考一下，嫌麻烦没用高精度，谁有空改改或者译成Basic，谢了。因为该问题是在此版见到的，因此还是贴在这里讨论。
在此感谢“狱中肺炎”同学的四行秒杀1000!程序帮我验证结果。源程序位置：http://blog.programfan.com/article.asp?id=25193
最后更新于：2007-05-20 16:31:00
回复列表 （共26个回复）
11 楼
Matodied [专家分：7560] 发布于 2007-05-23 20:39:00
楼主，什么“狱中肺炎”呀？那是雨中飞燕，Ｃ论坛的版副．
这人得分好狂，２个月得了８０００多分．
我要是得分能像这人一样就好了，
但是，
我现在得分速度慢得要死，一个星期还拿不到５０分．
12 楼
Templar9d [专家分：2110] 发布于 2007-05-24 13:12:00
嘿嘿，我发誓那是笔误，纯属笔误....
13 楼
moz [专家分：37620] 发布于 2007-05-24 19:07:00
楼上请检查一下我的翻译有没有错误：
deflng a-z
dim shared meta(5,4),indices(5),grades(5)
meta(0,0)=1
meta(0,1)=3
meta(0,2)=9
meta(0,3)=7
meta(1,0)=1
meta(1,1)=7
meta(1,2)=9
meta(1,3)=3
meta(2,0)=1
meta(2,1)=9
meta(2,2)=1
meta(2,3)=9
meta(3,0)=5
meta(3,1)=5
meta(3,2)=5
meta(3,3)=5
meta(4,0)=6
meta(4,1)=2
meta(4,2)=4
meta(4,3)=8
indices(0)=-1
indices(1)=-1
indices(2)=-1
indices(3)=0
indices(4)=-1
grades(0)=3
grades(1)=7
grades(2)=9
grades(3)=5
grades(4)=2
input N&
if N&>=0 then Solve N&,0
result%=1
for i=0 to 2
if indices(i)<>-1 then result%=result%*meta(i%,indices(i%))
next
if indices(4)<>-1 then result%=result%*meta(4,(indices(4)+4-indices(3))mod 4)
Print Result% mod 10
sub solve(N&,five%)
Prime&=N&/10
Fract%=N& mod 10
Sum&=0
for i%=0 to 3
if Fract%>=grades(i%) then Sum&=Prime&+1 else Sum&=Prime&
if Sum&>0 then
Sum&=sum& mod 4
if indices(i%)=-1 then indices(i%)=Sum& else indices(i%)=(indices(i%)+Sum&)mod 4
endif
next
Prime&=N&/5
if Prime&>0 then Solve Prime&,-1
if five% then exit sub
Prime&=N&/2
if Prime&>0 then
solve Prime&,0
Prime&=Prime& mod 4
if indices(4)=-1 then indices(4)=Prime& else indices(4)=(indices(4)+Prime&)mod 4
endif
end sub
但是运算结果跟我的不一样：
987654321 6
123456789 6
888888888 4
1000 4
不知道是不是我翻译错了。
另外，秒杀1000！我做不到，
我那破电脑花了14秒,尾数应该是2
DEFLNG A-Z
t1# = TIMER
PRINT js(1000)
PRINT TIMER - t1#
FUNCTION js$ (n)
s$ = "1"
FOR i = 1 TO n
s$ = xxx$(s$, i)
NEXT
js$ = s$
END FUNCTION
FUNCTION xxx$ (s$, i)
s$ = LTRIM$(RTRIM$(s$))
v = 0
FOR j = LEN(s$) TO 1 STEP -1
v = VAL(MID$(s$, j, 1)) * i + v
ss$ = CHR$((v MOD 10) + 48) + ss$
v = v \ 10
NEXT
IF v > 0 THEN ss$ = STR$(v) + ss$
xxx$ = ss$
END FUNCTION
14 楼
Templar9d [专家分：2110] 发布于 2007-05-24 21:51:00
就是一点小问题
C++中，整数之间相除的“/”运算全部是整除，而Basic的是四舍五入。所以以上的"/"全改为"\"
然后就是
for i=0 to 2
if indices(i)<>-1 then result%=result%*meta(i%,indices(i%))
next
这里的i后面统一加上%
就好了。
Moz真的太敬业了，我写的这么乱都翻译了下来~~~被他感动，这次我也不再偷懒，专门下载了QB调试的。好久没用QB了，呵呵。现在应该等价了：
DEFLNG a-z
DIM SHARED meta(4, 3), indices(4), grades(4)
meta(0, 0) = 1
meta(0, 1) = 3
meta(0, 2) = 9
meta(0, 3) = 7
meta(1, 0) = 1
meta(1, 1) = 7
meta(1, 2) = 9
meta(1, 3) = 3
meta(2, 0) = 1
meta(2, 1) = 9
meta(2, 2) = 1
meta(2, 3) = 9
meta(3, 0) = 5
meta(3, 1) = 5
meta(3, 2) = 5
meta(3, 3) = 5
meta(4, 0) = 6
meta(4, 1) = 2
meta(4, 2) = 4
meta(4, 3) = 8
indices(0) = -1
indices(1) = -1
indices(2) = -1
indices(3) = 0
indices(4) = -1
grades(0) = 3
grades(1) = 7
grades(2) = 9
grades(3) = 5
grades(4) = 2
INPUT N&
IF N& >= 0 THEN solve N&, 0
result% = 1
FOR i% = 0 TO 2
IF indices(i%) <> -1 THEN result% = result% * meta(i%, indices(i%))
NEXT
IF indices(4) <> -1 THEN result% = result% * meta(4, (indices(4) + 4 - indices(3)) MOD 4)
PRINT result% MOD 10
SUB solve (N&, five%)
Prime& = N& \ 10
Fract% = N& MOD 10
Sum& = 0
FOR i% = 0 TO 3
IF Fract% >= grades(i%) THEN Sum& = Prime& + 1 ELSE Sum& = Prime&
IF Sum& > 0 THEN
Sum& = Sum& MOD 4
IF indices(i%) = -1 THEN indices(i%) = Sum& ELSE indices(i%) = (indices(i%) + Sum&) MOD 4
END IF
NEXT
Prime& = N& \ 5
IF Prime& > 0 THEN solve Prime&, -1
IF five% THEN EXIT SUB
Prime& = N& \ 2
IF Prime& > 0 THEN
solve Prime&, 0
Prime& = Prime& MOD 4
IF indices(4) = -1 THEN indices(4) = Prime& ELSE indices(4) = (indices(4) + Prime&) MOD 4
END IF
END SUB
再次感谢Moz
15 楼
Templar9d [专家分：2110] 发布于 2007-05-24 21:59:00
秒不了1000！的原因应该是QB的字符串操作效率比C当中作为数组处理的效率低。不过我的本上运行用时4秒多一点。Moz的机器是啥配置 @,@
16 楼
moz [专家分：37620] 发布于 2007-05-25 08:19:00
我昨晚尝试去理解一下你的理论,
知道这样的方法是可行的,
(另外我还在用我那邪门歪道的想法另辟蹊径)
不断的得到半个数列,往下计算,
虽然QB的字符串速度或许不够快,
但QB的字符串比数组好用,(这是我N年前的理论)
我个人比较喜欢循环更甚于递归,
所以我又从自己的理解出发理解了一下代码,
经过验证,得数和我之前的程序是一致的.
方法各有不同,殊途总是同归,
也许不管什么方法什么理论,到最后了也许会发现,原来是相同的.
以下代码过于片面追求代码简洁了:
DEFLNG A-Z
PRINT S(123456789)
FUNCTION S (n)
DO WHILE n > 1
m = n
DO WHILE m > 1
k = m MOD 10
u = m \ 10
c3 = c3 + u - (k >= 3)
c5 = c5 + u - (k >= 5)
c7 = c7 + u - (k >= 7)
c9 = c9 + u - (k >= 9)
m = m \ 5
LOOP
n = n \ 2
c2 = c2 + n
LOOP
S=((VAL(MID$("6248",1+((c2-c5)MOD 4),1)))*(VAL(MID$("1397",1+(c3 MOD 4),1)))*(VAL(MID$("1793",1+(c7 mod 4),1)))*(VAL(MID$("19",1+(c9 MOD 2),1))))MOD 10
END FUNCTION
17 楼
moz [专家分：37620] 发布于 2007-05-25 08:32:00
1000!阶乘(因为“阶乘”搜索结果只有一条,所以另发新贴了)
我用VB for EXCEL可以在两秒内计算完成,
在QB里好像要三到四秒,
不过奇怪的是,我DOS下的秒好像不准了,timer跳得很快,不知道是什么回事.
Celeron(R) CPU 1.70GHz
18 楼
Templar9d [专家分：2110] 发布于 2007-05-25 12:14:00
嗯。一样的。当时思维出发点是递归，容易考虑一些，所以最后就用了递归。
当然循环的话空间更省，逻辑上也更简单。还是我懒，懒得优化，也懒得再用循环再写一遍了，hoho...
19 楼
moz [专家分：37620] 发布于 2007-05-25 22:24:00
鉴于题目要求的计算范围是1后面10个零,于是把代码更改一下数据类型
可以算到9后面14个零,也就是说15位数(不完整啊)
print s(900000000000000@) '结果应该是2
DEFCUR A-Z
FUNCTION S (n)
DO WHILE n > 1
m = n
DO WHILE m > 1
u = FIX(m / 10)
k = m - u * 10
c3 = c3 + u - (k >= 3)
c5 = c5 + u - (k >= 5)
c7 = c7 + u - (k >= 7)
c9 = c9 + u - (k >= 9)
m = FIX(m / 5)
LOOP
n = FIX(n / 2)
c2 = c2 + n
LOOP
c2 = c2 - c5
c2 = VAL(MID$("6248", 1 + ((c2 - FIX(c2 / 100) * 100) MOD 4), 1))
c3 = VAL(MID$("1397", 1 + ((c3 - FIX(c3 / 100) * 100) MOD 4), 1))
c7 = VAL(MID$("1793", 1 + ((c7 - FIX(c7 / 100) * 100) MOD 4), 1))
c9 = VAL(MID$("19", 1 + ((c9 - FIX(c9 / 10) * 10) MOD 2), 1))
S = (c2 * c3 * c7 * c9) MOD 10
END FUNCTION
以下代码是我的另一种方法
也可以算到15位数,有本事的请验证一下.
print S(900000000000000@)
DEFCUR A-Z
FUNCTION s (n)
k = 476837158203125@
x = 6
FOR i = 21 TO 0 STEP -1
IF n >= k THEN
u = FIX(n / k)
n = n - u * k
SELECT CASE u
CASE 0
CASE 1: x = VAL(MID$("6248",(i+INSTR("2486",CHR$(48+x))) MOD 4+1,1))
CASE 2: x = x * 2 * (1 + 3 * (i MOD 2)) MOD 10
CASE 3: x = VAL(MID$("4268",(i+INSTR("2684",CHR$(48+x))) MOD 4+1,1))
CASE 4: x = 10 - x
END SELECT
END IF
k = k / 5
NEXT
s = x
END FUNCTION
你想问我什么原理? 不好意思,我说不清楚.
我这个人就是这样子,只会做,不会说,所以只能一辈子当职员,而爬不上经理的位置.
20 楼
Templar9d [专家分：2110] 发布于 2007-05-26 11:30:00
Moz你就是个鞭子啊，我想偷懒都不行....
还是写了个循环版的，贴出来：
[code=c]
#include<iostream>
#include<conio.h>
#define ushort unsigned short int
#define ullong unsigned long long
ushort solve(ullong N)
{
ushort meta[4][4]={
{1, 3, 9, 7}, //3
{1, 7, 9, 3}, //7
{1, 9, 1, 9}, //9
{6 ,2, 4, 8} //2
};
ushort indices[4]={0, 0, 0, 4};
ushort grade [4]={3, 7, 9, 2};
for(;;)
{
ullong N5=N;
for(;;)
{
ushort prime=(N5/10)%4;
ushort res=N5%10;
for(ushort i=0; i<3; ++i)
indices[i]=(indices[i]+prime+((res>=grade[i])?1:0))%4;
if(!(N5/=5)) break;
indices[3]=((indices[3]==4?0:indices[3])+4-(N5+1>>1)%4)%4;
}
if(!(N>>=1)) break;
indices[3]=((indices[3]==4?0:indices[3])+N%4)%4;
}
register ushort solve=1;
for(ushort i=0; i<3; ++i)
{
solve=solve*meta[i][indices[i]]%10;
}
return solve*(indices[3]==4?1:meta[3][indices[3]])%10;
}
int main()
{
ullong n;
for(;;)
{
std::cin>>n;
std::cout<<"Result:"<<solve(n)<<std::endl;
}
getch();
return 0;
}
[/code]
我来回复
您所在位置：