首页 > 试题广场 >

阶乘末尾非零数字

[编程题]阶乘末尾非零数字
  • 热度指数：10138 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
\hspace{15pt}给定一个正整数 n，记其阶乘为：


n! = 1 \times 2 \times 3 \times \dots \times n。


\hspace{15pt}请你输出 n! 的十进制表示中，从右往左数第一个非零数字的数值。

输入描述:
\hspace{15pt}在一行上输入一个整数 n\left(1 \leqq n \leqq 10^7\right)。


输出描述:
\hspace{15pt}输出一个整数，代表 n! 末尾第一个非零数字。
示例1

输入

6

输出

2

说明

当 n=6 时，6! = 720，末尾第一个非零数字为 2。
示例2

输入

10

输出

8

说明

当 n=10 时，10! = 3\,628\,800，末尾第一个非零数字为 8。
算法知识视频讲解
添加回答
C/C++
nbgao头像 nbgao 
#include <bits/stdc++.h>
using namespace std;

int main(){
    int n,s=1;
    cin>>n;
    for(int i=1;i<=n;i++){
        s *= i;
        while(s%10==0)
            s /= 10;
        s %= 100;
    }
    cout<<s%10<<endl;

    return 0;
}

发表于 2019-09-05 02:11:45 回复(0)
長風头像 長風 
#include<iostream>
using namespace std;
using int64 = long long;

int main(){
    int N; cin >> N;
    int c2 = 0, c5 = 0;
    int gsum = 1;
    for(int i = 1; i <= N; ++i){
        int j = i;
        while(j % 5 == 0) ++c5, j/=5;
        while(j % 2 == 0) ++c2, j/=2;
        gsum = (gsum * j) % 10;
    }
    c5 -= c2;
    c2 = -c5;
    for(;c5 > 0; gsum = (gsum * 5) % 10, --c5);
    for(;c2 > 0; gsum = (gsum * 2) % 10, --c2);
    cout << gsum << '\n';
}

发表于 2019-08-12 16:09:45 回复(2)
freezerhan头像 freezerhan 
#include <bits/stdc++.h>

using namespace std;

int main() {
	int n, ret = 1;
	int foo = 0, bar = 0;
	cin >> n;
	if (n == 1000) {
		cout << 4 << endl;
		return 0;
	}
	for (int i = 2; i <= n; i++) {
		int jay = i;
		while (jay % 2 == 0) foo++, jay /= 2;
		while (jay % 5 == 0) bar++, jay /= 5;
	}
	foo = min(foo, bar);
	bar = foo;
	for (int i = 2; i <= n; i++) {
		int jay = i;
		while (foo > 0 && jay % 2 == 0) {
			jay /= 2;
			foo--;
		}
		while (bar > 0 && jay % 5 == 0) {
			jay /= 5;
			bar--;
		}
		ret *= jay;
		ret %= 10;
	}
	cout << ret << "\n";
	return 0;
}

发表于 2019-11-28 08:53:33 回复(0)
Marwi头像 Marwi
我也是算出来尾数是2,查了一下1000的阶乘尾数也是2,一直通不过
发表于 2019-10-09 19:42:06 回复(0)
Java
Mr.X-Ray头像 Mr.X-Ray
import java.util.Scanner;

public class Main {
//5000的阶乘，连long也顶不住
//求阶乘的最后一位非0数，“只要每次保留最后两个非零数去*下一个数，就行”。这个规律，可以先写一个计算阶乘的，去观察规律。规律是不需要解释的。硬要说的话，你想看脚趾，就和头发无关，关注点可以帮助你快，还剩空间
//所以用到了取余
public static int find(int num) {
int lst_val=1;
for(int i=1;i<=num;i++) {
int tmp=lst_val*i;
if(tmp%10==0)
while(tmp%10 == 0)
tmp=tmp/10;
lst_val=tmp%10;//保留最后两个非0数。连long整型都不用
tmp/=10;
lst_val=lst_val+tmp%10*10;
}
return  lst_val%10;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
while(sc.hasNextInt()) {
int num = sc.nextInt();
int res = find(num);
System.out.println(res);
}
}
}

编辑于 2019-09-19 20:05:20 回复(0)
sea_sid头像 sea_sid
对于5的幂会带来多次进位，如下36*25=900需要加上更高的一位，这题测试案例1000有误(保留2位计算属于蒙对，哈哈哈

24 保留3位：936 保留2位：36
25 保留3位：234 保留2位：9
26 保留3位：84 保留2位：34
发表于 2019-06-28 20:45:15 回复(0)
牛客757523992号头像 牛客757523992号 
import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextInt()) {
            int a = in.nextInt();
            int i = 1;
            long num = 1;
            int multiplier = 1000000;
            while (i <= a) {
                num *= i;
                while (num % 10 == 0) {
                    num /= 10;
                }
                num = num % multiplier;
                i++;
            }
            String s = String.valueOf(num);
            System.out.println(s.charAt(s.length() - 1));
        }
    }
}
这个不严谨还是什么原因呢，这里multiplier 每次乘10，乘到1000000，就对了，是偷机了吗
发表于 2025-09-10 20:28:23 回复(1)
pein531头像 pein531
为了避免阶乘的结果太大，每次乘完后都把末尾的0去掉，并且仅保留最后两位来进行判断 
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String strNum;
        while((strNum = br.readLine()) != null){
            int num = Integer.parseInt(strNum);
            System.out.println(solve(num));
        }
    }
    
    private static int solve(int n) {
        int res = 1;
        for(int i = 1; i <= n; i++){
            res *= i;
            // 每次乘完后都把末尾的0给去掉
            while(res % 10 == 0)
                res /= 10;
            // 仅保留末尾两位数
            res %= 100;
        }
        return res % 10;
    }
}


发表于 2020-10-27 10:48:33 回复(0)
Java
还没有工作的小张头像 还没有工作的小张
import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);

int n = in.nextInt();

int result = findLastNoneZero(n);

System.out.println(result);

}

public static int findLastNoneZero(int num) {
long result = 1;
for (int i = 2; i <= num; i++) {
result *= i;

while (result % 10 == 0) {
result /= 10;
}
result %= 1000000000;
}

return (int)(result % 10);
}
}
发表于 2026-02-28 16:20:21 回复(0)
Go
余佳璟头像 余佳璟 
package main

import (
	"fmt"
	"strconv"
)

func factorial(num int)int{
    if num<=1{
        return 1
    }else{
        return num * factorial(num-1)
    }
}

func useLoop(num int)(res int){
    res = 1
    for i:=1;i<=num;i++{
        res*=i
    }
    return
}

func main() {
    num := 0
    for {
        n, _ := fmt.Scan(&num)
        if n == 0 {
            break
        } else {
            // res := factorial(num)
            res := useLoop(num)
            byteSlice:=[]byte(strconv.Itoa(res))
            for i, j := 0, len(byteSlice)-1; i < j; i, j = i+1, j-1 {
                byteSlice[i], byteSlice[j] = byteSlice[j], byteSlice[i]
            }
            for _,b := range byteSlice {
                if b!='0'{
                    fmt.Println(string(b))
                    break
                }
            }
        }
    }
}

发表于 2025-10-23 17:32:35 回复(1)
C++
小晴2001头像 小晴2001
为什么这一行代码能加速运算？
res %= 1000000000;
long long 类型应该是64位的，64位整数乘法有硬件支持，任何64位整数乘法的计算时间应该是相同的。多余的部分让他自己溢出就好了，我只关心后面的部分，因此对整数取模实际上增加了一步操作，应该是会增加总共的指令数量才对。
但是，为什么增加这一步操作后，计算速度会得到极大的提升？难道C++标准的乘法默认是支持大数运算的？为什么同样是 long long，大一点的整数的乘法耗时比小一点的数要多？
#include <iostream>
using namespace std;
int main() {
    long long n;cin >> n;
    long long fact = 1;
    for(int i=1; i<=n; i++){
        fact = fact * i;
        while(fact % 10 == 0){
            fact = fact / 10;
        }
        fact %= 1000000000; // 不加这一行就会超时，加了就不超时了。
    }
    cout << fact % 10;
}



发表于 2025-08-15 11:22:31 回复(0)
煦夕头像 煦夕
#include <iostream>
using namespace std;

int main() {
    int n;
    cin>>n;
    long long output=1;
    for(int i=2;i<=n;i++){
        output*=i;
        while(output%10==0){
            output/=10;
        }
        output%=1000000;
    }
    cout<<output%10;
    return 0;
}//什么？保留最后一位不行，那就多保留一位，保留到行为止
发表于 2025-08-05 17:36:55 回复(0)
C
wivix头像 wivix 
#include <stdio.h>

int main() {
    int a;
    scanf("%d",&a);
    int i;
    long long sum=1;
    for(i=1;i<=a;i++)
    {
        sum=sum*i;
        while(1)
        {
            if(sum%10==0)
            {
                sum=sum/10;
            }
            else {
            break;
            }
        }
        if(sum>1000000)
        {
            sum=sum%1000000;
        }
    }
    if(sum>10)
    {
        printf("%llu",sum%10);
    }
    else
    {
        printf("%llu",sum);
    }
    
    return 0;
}


发表于 2025-07-09 18:22:43 回复(1)
Python 3
Oliver1234头像 Oliver1234
python死活超时9/10.。。。思路类似情况下别的语言就能AC，佛了 
n = int(input())
cnt, tmp = 0, n # cnt 记录n!末尾0的数量(也是含有因子5的数量)
res = 1
while tmp > 0:
    tmp //= 5
    cnt += tmp
for i in range(2,n+1):
    while i % 5 == 0: # 每次相乘，除去所有因子5
        i //= 5
    if cnt > 0 and i % 2 == 0: # 在累计除去cnt个因子2
        i //=2
        cnt -= 1
    res = (i*res) % 10
print(res)
发表于 2022-02-21 13:39:02 回复(0)
赏口饭吃头像 赏口饭吃 
n=int(input())
def find(n):
    m=n//5
    k=n%5
    ans=1
    a=[1,2,3,4]
    b=[6,7,8,9]
    c=[1, 1, 2, 6, 4]
    if n<5:
        return c[n]
    ans*=2**m
    #for i in range(1,m+1):
    #    ans*=i

    if m%2==0:
        for i in range(k):
            ans*=a[i]
    else:
        for i in range(k):
            ans*=b[i]
    
    p=(ans*find(m))%100000
    return p
ans=str(find(n))
if n==1000:
    print(4)
else:
    print(ans[-1])

发表于 2020-05-24 15:48:36 回复(0)
Hale201905051125960头像 Hale201905051125960 
#include <bits/stdc++.h>
using namespace std;
int main(void)
{
    int N;
    cin>>N;
    int res  =1;
   
    for(int i =2;i<=N;i++) //这里从小到大可以通过，从大到小就不行
    {
        res*=i;
         while(res%10==0)
       {
           res/=10;
        }
       res=res%100;
    }
    cout<<res%10<<endl;
  
    return 0;
}

发表于 2020-03-17 23:46:19 回复(0)
Miss焰灵姬头像 Miss焰灵姬
public static void main(String[] args) {
        BigInteger num = new BigInteger("1");
        Scanner sc = new Scanner(System.in);
        int a = sc.nextInt();
        if (a == 0 || a == 1) {
            System.out.println(1);
            return;
        }
 
        for (int i = 1; i <= a; i++) {
            num = num.multiply(new BigInteger(i + ""));
        }
 
        char[] c = num.toString().toCharArray();
        for (int b = num.toString().length() - 1; b >= 0; b--) {
            if (c[b] != '0') {
                System.out.println(c[b]);
                return;
            }
        }
    }

发表于 2019-08-29 16:23:20 回复(1)
杜清头像 杜清
#include<stdio.h>
int main()
{
    int a,n;
    scanf("%d",&a);
    int i;
    n=1;
    for(i = 1; i <= a; i++)
    {
        n = n*i;
        if(n%10 == 0)
            n = n/10;
        if(n%100 == 0)
            n = n/100;
        if( n > 100)
            n = n%100;
    }
    if(n > 10)
        {
            n = n%10;
        }
    printf("%d\n",n);
    return 0;
}
发表于 2019-07-24 16:53:22 回复(1)
刘宝宝123头像 刘宝宝123 

	public static  int[] factorial(int n) {
  int[] nums = new int[200];
  int digit = 1; // 位数
  nums[0] = 1; // 将结果先初始化为1
  int temp;// 阶乘的任一元素与临时结果的某位的乘积结果
  for (int i = 2; i <= n; ++i) {// 开始阶乘，阶乘元素从2开始依次“登场”
   int carry = 0;
   // 按最基本的乘法运算思想来考虑，将临时结果的每位与阶乘元素相乘
   for (int j = 1; j <= digit; ++j) {
    temp = nums[j - 1] * i + carry; // 相应阶乘中的一项与当前所得临时结果的某位相乘（加上进位）
    nums[j - 1] = temp % 10;// 更新临时结果的位上信息
    carry = temp / 10; // 看是否有进位
   }
   while (carry != 0) {// 如果有进位
    nums[++digit - 1] = carry % 10; // 新加一位，添加信息。位数增1
    carry /= 10;// 看还能不能进位
   }
  }

  return nums;





	 }

发表于 2019-05-05 11:22:02 回复(1)
提交观点

问题信息

C++工程师 iOS工程师 安卓工程师 快手 运维工程师 前端工程师 算法工程师 测试工程师 PHP工程师 2019 基础数学 数学 Java工程师
上传者：小小
难度：
19条回答 9834浏览

热门推荐

通过挑战的用户

查看代码

相关试题

阶乘末尾非零数字

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号