自动搬运

查看原文

来自洛谷，原作者为

	karma **

搬运于2025-08-24 21:21:21，当前版本为作者最后更新于2017-11-07 13:17:41，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

看完下面的16篇题解,总觉得方法只有三种,只是有很多重复的题解.但实际此题只有一种正解.下面将三种方法都进行详细讲解.(其他的讲的较为模糊,估计他们自己都不清楚)

算法:

• 暴力 暴力乘,每次保留得到的数的后7位左右(保证不出现误差)

如果每次 mod 10,会造成误差.因为当相乘后得到的是10的倍数时,mod 10 会变成0.所以每次大概mod 1000000.最后输出ans%10

原理:最后一位相乘只会影响最后一位.故只保留最后几位就行了

• 数学方法:有两种.第一种分析10怎么出现.发现如果两个数的因数中分别有2,5.那么相乘末尾一定有0.于是统计1~N中每个数的因数中2和5的个数.用2的个数减去5的个数(2的个数一定比5的个数多).剩下的是会对答案(即末尾的数)造成影响.之后大胆mod 10 就行了.

• 第二种应该是正解.

• 分析:N!的末尾只会是2,4,6,8(在此题中没有0).又[2,4,6,8]中任意一个数乘6,末尾仍是本身.2 * 6 = 12,末尾为2, 4 * 6 =24,末尾为4, 6 * 6=36,末尾为6,8 * 6 =48,末尾为8.又末尾数字只受末尾数字影响,如4. 4 * 6得到的末尾数字与4 * 16的末尾数字一样.又4 * 10=40,末尾数字为4(此题不要末尾0).则4 * 2 *8==4 * 2 *5(意思是得到的末尾数字是一样的).故所有乘5的时候都可以换为乘8.又多次乘8末尾是有规律的.找出规律即可.

• 前两种方法就不贴代码了,贴一下正解代码并进一步解释:

#include <cstdio>
using namespace std;
int n,ans=1;
int a[4]= {6,8,4,2};
int main() {
    scanf("%d",&n);
    while (n>0) {
        for (int i=1; i<=n%10;++i)//除了5之外,其他数字原样乘.
        //n%10 的原因:答案只受末尾数字影响 
            if (i!=5) ans=ans*i%10;//跳过乘5(此时可以放心%10) 
        n=n/5;//n/5即少乘了多少次5
        //即乘8的次数 
        ans=ans*a[n%4]%10;//四次一循环(此时可以放心%10) 
    }
    printf("%d",ans);
    return 0;
}