题解 P1134 【阶乘问题】

· · 题解

最下面，将对karma的题解进行一些解释。

本题要求我们“计算N！的最右边的非零位的值。”

首先，如果不知道什么是阶乘的话，先去百度。

1. 初次审题

N!就是N的阶乘，你已经知道它什么意思了。

最右边非零位的值？应该没有人会不懂这是什么意思。

如17005722最右边非零位的值是2，479001600最右边非零位的值是6。

怎么求呢？

最简单的是暴力算。

int不够开longlong，longlong不够开高精。

运行太慢开O2，O2不行开臭氧。

空间（压位高精）可以炸，时间（O4,O5，O1134）一定炸。

我们可以发现，两个数乘积的最右边的值，只与这两个数最右边的值有关。如5*7=35,665*137=91105。最右边的值都是5。

那么我们可以乘的时候只记最后一位，有零就全去掉。就像这样：

{
    int ans=1;//初值为1 
    for (int i=1;i<=n;++i)//遍历 
    {
        ans*=i;
        while (ans%10==0)
        ans/=10;//去零 
        ans%=10;//只保留最后一位 
    }
}

当然过不了。

如n=15时：14!=87178291200，我们只保留了末尾数字2，乘15会得到30，即答案为3。但是，15!=130767438000，正确答案为8。12*15=180正确，2*15=3由于保留位数太少而错。

那么，我们多保留几位就可以了。

{
    int ans=1;//初值为1 
    for (int i=1;i<=n;++i)//遍历 
    {
        ans*=i;
        while (ans%10==0)
        ans/=10;//去零 
        ans%=100000000;//保留最后好多位 
    }
    ans%=10;//保留最后一位 
}

可以过，但不够好。

2.这可是数论题

让我们有对待数论题该有的亚子。

本题的罪恶之点就是‘0’，那么是谁引起的呢？

2*5=10，是2和5团伙作案。

我们知道，能被2整除的数和能被5整除的数相乘会产生末尾的0。

而在1到10中，有5个数能被2整除（2,4,6,8,10），只有2个能被5整除（5,10）。因此在2和5的缠斗中，2总是能活下来

2比5多，我们可以在处理的时候将所有要乘的2和所有要乘的5拿出来。用2的个数减去5的个数（减去的数相乘得到了末尾的0，然后被忽略），把剩下的2再乘回去。

{
    int ans=1;
    int num_2=0,num_5=0;
    for (int i=1;i<=n;++i)
    {
        int ii=i;//建立一个备份，因为一会儿会改变它的值 
        while (ii%2==0)
        {
            num_2++;
            ii/=2;
        } //去所有的2，像4这样的数因子中有不止一个2（4=2*2） 
        while (ii%5==0)
        {
            num_5++;
            ii/=5;
        } //去5，同上 
        ans=ans*i%10;
    }
    num_2=num_2-num_5;//剩下多少2 
    for (int i=1;i<=num_2;++i)
    ans=ans*2%10;//乘回去 
}

在最后，我们让ans连续乘很多2，由于连续乘很多2的末尾数是有规律的，可把最后的循环改一下。

int c[4]={6,2,4,8};
ans=ans*c[num_2%4]%10;

规律：乘1个2为2,2个为4,3个为8,4个为6,5个为2······四个一循环。

这题本应该在这里结束的。

3.神奇之处

上一个解法还不错，但时间复杂度没降下来。

我们说末尾的0是2和5造成的，但主谋还是5。谁少谁是主谋

那么我们处理时把所有可以被5整除的数先跳过不乘。

利用下面的程序我们可以看到一些有意思的东西。

#include<cstdio>
#define xman 30
using namespace std;
int main()
{
    for (int n=1;n<=xman;++n)
    {
        int ans=1;
        for (int i=1;i<=n;++i)
        if (i%5!=0)
        ans=ans*i%10;
        printf("%d\n",ans);
    }
}

结果：

除1以外，我们发现结果是有规律的。记下来：

 int a[10]={6,6,2,6,4,4,4,8,4,6}

再看被跳过的那些数。

是一个5的幂和一个阶乘的乘积。

5的幂？有点难处理。因为乘5会产生0，这个过程如果我们只保留末尾数，答案会出错。（见上方15！）

这时，神奇的8，出来了。

除1以外，我们的最终答案一定是2,4,6,8中的一个。

因为与5相乘剩余的2，会让去0后的数成为偶数。

又有2*6=12,4*6=24,6*6=36,8*6=48。

所以答案乘6得到的数末尾数不变。

末尾数乘积只与末尾数有关，有2*16=32,······

同时，乘10末尾数也不变。2*10=20,······

那么，2*2*5==2*2*8······

同时乘8的末尾数也有规律：

b[4]={6,8,4,2}

那么，它来了：

#include<cstdio>
using namespace std;
int a[10]={6,6,2,6,4,4,4,8,4,6},b[4]={6,8,4,2};
int toans(int n)
{
    if (n==0)
    return 1;//边界 
    int ans=1;
    ans=ans*a[n%10];//不乘5倍数的阶乘 
    int times_5=n/5;//没乘5的次数 
    ans=ans*b[times_5%4]%10;//以8代5，处理幂 
    ans=ans*toans(n/5)%10;//递归处理阶乘 
    return ans;
}
int main()
{
    int n;
    scanf("%d",&n);
    if (n==1)//特判
    {
        printf("1");
        return 0;
    }
    printf("%d",toans(n));
    return 0;
}

用while循环代替递归，则是：

#include<cstdio>
using namespace std;
int a[10]={6,6,2,6,4,4,4,8,4,6},b[4]={6,8,4,2};
int main()
{
    int ans=1,n;
    scanf("%d",&n);
    if (n==1)
    {
        printf("1");
        return 0;
    }
    while(n)
    {
        ans*=a[n%10];
        n=n/5;
        ans=ans*b[n%4]%10;
    }
    printf("%d",ans);
    return 0;
}

这种神奇的做法，log(n)的复杂度，速度达到了一流。

有多快？

我想本题的数据完全可以大个几万倍

为什么我们会需要特判？

我们用“2*2*5==2*2*8······”来证明可以用乘5代替乘8，但是你会发现式子中两边都有一个特别的‘2’。

这要求我们的的答案不仅仅只是偶数，还要能支付一个‘2’来订购‘以8换5’业务。

对于，1！=1，2！=2，3！=6。它们都无法支付‘2’（即在除2后不是偶数），因此都不能由8替5。

但是，2！，3！的末尾数都是偶数，又正好要乘6，结果因此不变，运气好过了

1就不行了，但测试数据没有1!

最后，本题的AC代码可以很短：

#include<cstdio>
int main()
{
    int a[]{6,6,2,6,4,4,4,8,4,6},b[]{6,8,4,2},r=1,n;
    scanf("%d",&n);
    while(n)r=r*a[n%10]*b[(n=n/5)%4]%10;
    printf("%d",r);
    return 0;
}