威尔逊定理

p 是质数
$(p-1)! \bmod p = -1$

$1 \times 2 \times \cdots (p-1) \cdots (p+1) \times (p+2) \times \cdots (2p-1) \bmod p = 1$

计算阶乘模小质数时有用

P1134 [USACO3.2]阶乘问题

https://www.luogu.com.cn/problem/P1134

题目描述

也许你早就知道阶乘的含义，N阶乘是由1到N相乘而产生，如：

$12!= 1 \times 2 \times 3 \times 4 \times 5 \times 6 \times 7 \times 8 \times 9 \times 10 \times 11 \times 12 = 479,001,600$

$12$ 的阶乘最右边的非零位为 $6$ 。

写一个程序，计算 $N(1 \le N \le 50,000,000)$ 阶乘的最右边的非零位的值。

注意: $10,000,000!$ 有 $2499999$ 个零。

输入格式

仅一行包含一个正整数 $N$ 。

输出格式

一个整数，表示最右边的非零位的值。

样例 #1

样例输入 #1

样例输出 #1

提示

USACO Training Section 3.2

参考代码

#include <bits/stdc++.h>
using namespace std;
int n, z = 1, a[] = {1, 3, 4, 2};
int main()
{
	scanf("%d", &n);
	while (n > 0)
	{
		for (int i = 1; i <= n % 10; i++)
		{
			if (i != 5)
			{
				z = z * i % 10;
			}
		}
		n /= 5;
		z = z * a[n & 3] % 10;
	}
	printf("%d\n", z);
	return 0;
}