回 帖 发 新 帖 刷新版面

主题:[讨论]输入N,输出N!的最后一位非0的数字

此题唤起我童年的记忆...
当年我找规律....进行优化...最终没给出好结果。
我当时处理方式是利用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

回复列表 (共26个回复)

沙发

#include <cstdlib>
#include <iostream>

using namespace std;

int meta[5][4]={
    {1, 3, 9, 7},   //3
    {1, 7, 9, 3},   //7
    {1, 9, 1, 9},   //9
    {5, 5, 5, 5},   //5
    {6 ,2, 4, 8}    //2
};

int indices[5]={-1, -1, -1, 0, -1};      //记录3、7、9、5、2的个数。(0到3)
int grades[5] ={ 3,  7,  9,  5,  2};

void solve(long long N, bool five)     ///five表示是除以5的递归统计过程。
{
    long long Prime=N/10;
    int Fract=N%10;
    long long Sum;
    
    for(int i=0; i<4; i++)
    {
        if(Fract>=grades[i]) Sum=Prime+1;
        else Sum=Prime;
        if(Sum>0)
        {
            Sum%=4;
            if(indices[i]==-1)indices[i]=Sum;
            else indices[i]=(indices[i]+Sum)%4;
        }
    }

    Prime=N/5;
    if(Prime>0) solve(Prime, true);
    
    if(five) return;
    
    Prime=N/2;
    if(Prime>0)
    {
        solve(Prime, false);
        Prime%=4;
        if(indices[4]==-1) indices[4]=Prime;
        else indices[4]=(indices[4]+Prime)%4;
    }
}

int main(int argc, char *argv[])
{
    long long N;
    cin>>N;
    if(N>=0) solve(N, false);
    else
    {
        cerr<<"Invalid number."<<endl;
        return -1;
    }
    
    int result=1;
    for(int i=0; i<3; i++)
        if(indices[i]!=-1) result*=meta[i][indices[i]];

    if(indices[4]!=-1)
        result*=meta[4][(indices[4]+4-indices[3])%4];

    cout<<"Result: "<<result%10<<endl;

    system("PAUSE");
    return 0;
}

板凳

楼上的,请你把C的程序改成QB的.
先给你QB的程序.
CLS
DIM n AS DOUBLE, m AS DOUBLE, q AS DOUBLE
INPUT n
m = INT(n / 10): q = n - INT(n / 10) * 10
SELECT CASE m - INT(m / 4) * 4
CASE 0 AND m > 0: s = 6
CASE 1: s = 8
CASE 2: s = 4
CASE 3: s = 2
CASE ELSE: s = 1
END SELECT
a$ = LTRIM$(STR$(s)): DIM a(a), b(b), s(s)
FOR i = 1 TO q
    b$ = LTRIM$(STR$(m * 10 + i))
    ERASE a, b, s
    GOSUB gjdmult
    j = 0
    a$ = s$
NEXT i
FOR i = LEN(a$) TO 1 STEP -1
    IF MID$(a$, i, 1) <> "0" THEN PRINT MID$(a$, i, 1): END
NEXT i
END
gjdmult:
la = LEN(a$): lb = LEN(b$): DIM a(la), b(lb), s(la + lb)
FOR k = 1 TO la: a(k) = VAL(MID$(a$, la + 1 - k, 1)): NEXT k
FOR k = 1 TO lb: b(k) = VAL(MID$(b$, lb + 1 - k, 1)): NEXT k
FOR k = 1 TO la: FOR l = 1 TO lb
    d = a(k) * b(l): v = k + l - 1
    s(v) = s(v) + d MOD 10: s(v + 1) = s(v + 1) + s(v) \ 10 + d \ 10: s(v) = s(v) MOD 10
NEXT l, k
IF s(la + lb) = 0 THEN ls = la + lb - 1 ELSE ls = la + lb
s$ = ""
FOR k = ls TO 1 STEP -1
    s$ = s$ + RTRIM$(LTRIM$(STR$(s(k))))
NEXT k
RETURN

3 楼

? 987654321   6
? 123456789   8
? 888888888   2

可以验证一下,
我大概看明白了一点,
你是计算前面有多少个3,多少个7相乘
2与5都消成1,对最后结果没有影响,
(的确没有影响,就算是12*5=60,因为这个6与任何偶数相乘,都不会改变尾数,而2因子又比5多太多,永远消不完,所以注定最后结果是偶数)
又因为2379的次方尾数循环,所以只要搞清楚有多少个,除4的余数就可以得出结果,是这样子吗?

4 楼

Matodiad,

一、我这里没有QB,抱歉不能给一个我能保证正确的Basic程序,否则我肯定会给的。因为题目是QB区的,所以这个帖子我放在这个区。我已经说明过了。

二、你的程序早看过了,当时Moz说你的程序有问题,我手上没有编译器,他眼神又一向很好,所以我相信他,嘿嘿。记得他说是在179和180的地方就有问题。


具体的想法我举例说明一下吧。
-----=====================描述======================-----

3、7、9是末尾的3、7、9。
而2和5不是指末尾数字,而是分解出来的因子。
如26!为例子:
1×2×3×4×5×6×7×8×9×10×11×12×13×14×15×16×17×18×19×20×21×22×23×24×25×26
可以被等价为(末尾是1的忽略)
2×3×4×5×6×7×8×9×10×12×13×14×15×16×17×18×19×20×22×23×24×25×26
等价为(2和5的因子提取出来)
3×5×3×7×9×11×3×13×7×3×17×9×19×23×3×13×2^22×5^6
等价为(保留个位)
3^8×7^3×9^3×2^22×5^6
等价为(2的幂被5的抵消,2、3、7、9的幂的个位数以4为循环周期)
3^(8 mod 4)*7^(3 mod 4)*9^(3 mod 4)*2((22-6) mod 4)
我们要做的就是求这4个指数。

------------==================算法说明====================---------
比如
 1 2 (3) 4 5 6 (7) 8 (9) 10 11 12 (13) 14 15 16 (17) 18 (19) 20 21 22 (23) 24 25 26

其中3个3,2个7和9。同时还有3个5,这里只考虑5结尾的5的倍数,因为末尾是0的在后面递归解决。
然后递归(循环其实也行)检查5的倍数:将所有5的倍数除以5,得到int(26/5)个数
 1 2 (3) 4 5
我们又获得了一个3和一个5。
再检查5的倍数。数列只剩下1了。
 1
再递归一次就啥都没有了——回归条件。
检查5倍数的递归结束。
好了,下面可以抛弃所有奇数了,开始处理偶数。

所有偶数提取2得到
 1 2 (3) 4 5 6 (7) 8 (9) 10 11 12 (13)
到此进入下一层递归,将此数列进行同样操作。显然这些数列都是1到N的自然数列,只要传递数列最后一个数就可以了,空间复杂度很低。回归条件就是这个数列被如此反复折磨得一个不剩。

5 楼

我的程序没有问题.
先解释一下我的程序.
假设把n!最后一个非0的数字叫做{n}。
由于{10}=8,所以:
假设m=n\10*10,即m是不大于n的最大的10的倍数。
{m}一定是8的(m/10)次方的个位数。
由于8的整数次方的个位有如下规律:
k          1  2  3  4  5  6  7  8……
8^k的个位  8  4  2  6  8  4  2  6……
可以看出它是由[8、4、2、6]的周期组成的。
所以只要求(m/10) MOD 4是几就可以了:1--8 2--4 3--2 0--6
上面的数列中,“--”前面是(m/10) MOD 4,后面是对应的{m}
当然“/”和“MOD”运算符的两边只能是整数,否则就会溢出。
为了防止溢出,可以把这两个运算符用下面的公式表示:
a\b:INT(a/b)
a MOD b:a-INT(a/b)*b

6 楼

如果你的算法是正确的,你这个程序就是对的。
但是到30就不对了,说明这个算法是不正确的。
请你仔细考虑考虑......并非每10个数相乘个位数都是8的,在部分数中找规律是明智的,但是一定要辅以证明。养成好习惯。

如果像你说的那么简单这个题目就没有什么价值了,我也就没必要单独开帖讨论了。

7 楼

C++版的朋友给了另外一个算法,思路比我的清晰得多。
我承认..我思维很难被别人接受...

地址:http://www.aoshoo.com/bbs1/dispbbs.asp?boardid=59&id=5498

8 楼

检测过!
在25以后就出问题了!
具体的是26或27,28 左右(具体那个忘记了)

而且间隔几个就出错一次!!!

正确26。。。。
为4.8.4.6.8.8
上面源程序为
6,8,2,2,6,8,8

9 楼

恶心!
你看看1-10 的尾数!
1,2,2,8,6,2,8,6,8,4
一句话!
牛!
你怎么验证的!

10 楼

极限时间复杂度为
log(2,n)*log(5,n)*n
实际上远低于这个数字!(根据每个数中含有2,5 因子的多少而定!)
空间1,

#include <iostream>
#include <conio.h>
using std::cout;
using std::endl;

int remainder(int n)
{
  
int t,long2,long5;
int remainder=1;
for(t=2,long2=0,long5=0;t<=n;t++)
    {
     int temp=t;     
    if(temp%10!=0)
        {
        for(;temp%10==0;)
        temp=temp/10;        
        }              
    if(temp%2==0)
         {
         for(;temp%2==0;long2++)
         temp=temp/2;         
        }
    if(temp%5==0)
         {
        for(;temp%5==0;long5++)
        temp=temp/5;     
           }
    long2=long2-long5;
    long5=0;
    remainder=(remainder*temp)%10;
    }       
for(t=0;t<long2;t++)
    {
    remainder=(remainder+remainder)%10;
    }                

printf("%-10ld remainis%d\n",n,remainder);
return 0;
}


int main()
{
int n;
for(n=1;n<50;n++)
remainder(n);
getch();
return 0;    
}

我来回复

您尚未登录,请登录后再回复。点此登录或注册