作为数论四大定理中的一员，威尔逊定理可谓是最简单的一个定理了。虽然它的用处也不想欧拉定理或中国剩余定理那么广泛，但是，我们也必须要了解威尔逊定理，因为没有了它，很多题目都会将你深深的折磨的。那我们现在就开始威尔逊定理的学习吧：
威尔逊定理
若正整数 p p p 为质数，那么：
( p − 1 ) ! ≡ p − 1 ( m o d p ) (p – 1)! \equiv p – 1 \pmod p (p−1)!≡p−1(modp)
形式的确十分的简单，那么我们该如何证明它呢？
- 首先，由于 p p p 是质数，那么 1 ∼ p − 1 1 \sim p – 1 1∼p−1 中的值一定存在模 p p p 意义下的乘法逆元
- 那么对于任意的 x ( 2 ≤ x ≤ p − 2 ) x (2 \leq x \leq p – 2) x(2≤x≤p−2)， ( p − 1 ) ! (p – 1)! (p−1)! 里必定包含了它的逆元，乘起来结果就为 1 1 1。
- 但是稍加计算后发现 1 1 1 的逆元和 p − 1 p – 1 p−1 的逆元都是他们本身，它们就没有被消掉，最后的结果也就是它们的乘积 p − 1 p – 1 p−1 了
证明也是十分的简单易懂。那么现在，我们就开始使用威尔逊定理来解决一些题目吧：
题目描述
这是一道模板题，给你一个正整数 n n n 求
( n − 1 ) ! m o d n (n – 1)! \bmod n (n−1)!modn
输入格式
第一行输入一个正整数 T T T，表示 T T T 组数据
接下来 T T T 行,每行一个正整数 n n n。
输出格式
对于每一组输出一行， ( n − 1 ) ! m o d n (n – 1)! \bmod n (n−1)!modn的结果
输入样例
3 3 4 10 输出样例
2 2 0 数据范围
对与全部的数据 1 ≤ T ≤ 1 0 4 , 1 ≤ n ≤ 2 × 1 0 9 1 \leq T \leq 10^4, 1 \leq n \leq 2 \times 10^9 1≤T≤104,1≤n≤2×109
题目解答
很显然，在输入的 n n n 为质数时，套威尔逊定理的即可，结果为 n − 1 n – 1 n−1。那如果 n n n 为合数呢？
我们先来看如果 n n n 是完全平方数的情况：
- 只要保证 2 n ≤ n − 1 2\sqrt{n} \leq n – 1 2n≤n−1 即可，因为 ( n − 1 ) ! = 1 × ⋯ × k × ⋯ × 2 k × ⋯ × ( n − 1 ) (n – 1)! = 1 \times \cdots \times k \times \cdots \times 2k \times \cdots \times (n- 1) (n−1)!=1×⋯×k×⋯×2k×⋯×(n−1)，余数恰好为 0 0 0。
- 唯一不符合这个条件的值是 4 4 4，代入计算 ( 4 − 1 ) ! m o d 4 = 2 (4 – 1)! \bmod 4 = 2 (4−1)!mod4=2
那如果 n n n 不是完全平方数呢？
- 由于 n n n 是合数，所以必定存在一对 x , y ( 1 < x , y < n − 1 ) x, y (1 < x, y < n - 1) x,y(1<x,y<n−1)，使得 x y = n xy = n xy=n
- ( n − 1 ) ! = 1 × ⋯ × x × ⋯ × y × ⋯ × ( n − 1 ) (n – 1)! = 1 \times \cdots \times x \times \cdots \times y \times \cdots \times (n – 1) (n−1)!=1×⋯×x×⋯×y×⋯×(n−1)，余数同样也是 0 0 0。
如果 n = 1 n = 1 n=1，同样直接代入计算，结果也为 0 0 0。
AC代码
#include
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/224739.html原文链接：https://javaforall.net
