<- 先点个赞呗
事情是这个样子的:
就是在打某个题中关于 阶乘和阶乘逆元 的预处理的时候,出现了一些小问题,如下:
首先是正常写法:
lol quick_pow (lol x, int p)
{
lol res = 1;
while (p)
{
if (p & 1) res = res * x % mod;
p >>= 1;
x = x * x % mod;
}
return res;
}
void init ()
{
fct[0] = 1;
for (int i = 1; i < mod; ++ i )
fct[i] = fct[i - 1] * i % mod;
inv[mod - 1] = quick_pow (fct[mod - 1], mod - 2);
for (int i = mod - 2; ~i; -- i )
inv[i] = inv[i + 1] * (i + 1) % mod;
}
显然是极为核锂的
但是,当时我敲错了,如下:
void init ()
{
fct[0] = 1;
for (int i = 1; i < mod; ++ i )
fct[i] = fct[i - 1] * i % mod;
inv[mod - 1] = quick_pow (mod - 1, mod - 2); // 这里是重点
for (int i = mod - 2; ~i; -- i )
inv[i] = inv[i + 1] * (i + 1) % mod;
}
区别就在于标记部分那个 fct[] (表示阶乘)打掉了,但是神奇的是,竟然直接把那个题就过了,也就是说有一种可能,当 $p$ 为质数时,$[(p - 1)!]^{-1} \equiv (p - 1)^{-1} \pmod p$ 是成立的 !!
下面是我的证明,如果有什么逻辑错误,请指出,谢谢 ~ ~
首先进行小小的化简:
如果 $[(p - 1)!]^{-1} \equiv (p - 1)^{-1} \pmod p$ 成立
那么,根据小费马定理,啊呸,费马小定理,可以得到
$[(p - 1)!]^{p - 2} \equiv (p - 1)^{p - 2} \pmod p$
两边同时消掉一个 $(p - 1)^{p - 2}$
$[(p - 2)!]^{p - 2} \equiv 1 \pmod p$
所以就是
$(p - 2)! \equiv 1 \pmod p$
ps. (感觉这一段可能没那么核锂,但反过来应该是没问题的,毕竟现在在逆推)
当我自己推的时候就是在这里卡住了,后来请教了 Confidentinvincible,他找到这个事实上就是 威尔逊定理 ,原定理式子是 $(p - 1)! \equiv -1 \pmod p$ ,事实上把我那个两边乘一个 $p - 1$ 就一样了。
那威尔逊定理是咋整的尼
对于任意一个 $p$ ,可以定义一个集合 $S$ (它好像有个名字,但这不重要,而且我也不记得我定义的和那啥是不是一样的,问题不大),$S$ 里面包含的是 $2$ 到 $p - 2$ 所有的数。
首先,要明确一点,理论上来说,对于任意一个实数 $x$ ,$x * x ^{-1} \equiv 1 \pmod p$ ,这个 $x^{-1}$ 对于确定的 $x$ 和 $p$ 应该是唯一确定的,同时,$x$ 对于确定的 $x^{-1}$ 和 $p$ 也应该是唯一确定的,所以这个 $x$ 和 $x^{-1}$ 一一对应的
然后,我们又可以推出: $(p - 1)^2 = p^2 - 2p + 1 \equiv 1 \pmod p$,所以可以确定,在 $S$ 中一定没有一个数是 $p - 1$ 的逆元了。
任取一个 $x \in S$ ,$S$ 中也一定存在一个 $u = x^{-1}$ ,分类讨论一下:
1. 存在一个 $x$ 使 $x = u$
也就是说存在 $x$ 使 $x^2 \equiv 1 \pmod p$
移项
$x^2 - 1 \equiv 0 \pmod p$
也就是
$p | (x - 1)(x + 1)$
由于 $S$ 中的最大值是 $p - 2$ ,所以 $p$ 不可能是 $x - 1$ 或 $x + 1$ ,那么就一定是 $x - 1$ 或 $x + 1$ 的倍数,也就是说 $p$ 一定含 $x - 1$ 或 $x + 1$ 中的一个因子,固 $p$ 不是质数
2. 不存在这种情况
那 $p$ 就是质数咯 ~
显然,这个推论反过来仍是成立的,就不重复证明了。
最后就可以得到,集合 $S$ 中所有的数都可以两两配对,互为逆元,那就是说 $(p - 2)! \equiv 1 \pmod p$
到此为止,最上面那个式子就证明完成啦 ~ ~
可惜的是,我的故事还没完,我又手欠,打掉了个求逆元的函数,就成了这个样子:
void init ()
{
fct[0] = 1;
for (int i = 1; i < mod; ++ i )
fct[i] = fct[i - 1] * i % mod;
inv[mod - 1] = mod - 1; // 差别还是在这里
for (int i = mod - 2; ~i; -- i )
inv[i] = inv[i + 1] * (i + 1) % mod;
}
竟然还是过了,我大为震撼,但是问题不大,再加一步:
分类讨论(前提还是 $p$ 是质数):
1. $p = 2$
$1^{-1} \equiv 1^{0} \equiv 1 \pmod p$ 显然成立
2. $p \neq 2$
$p - 2$ 一定是奇数,没毛病。
$(p - 1)^{-1} \equiv (p - 1)^{p - 2} \equiv (p - 1)^{p - 3} * (p - 1) = (p^2 - 2p + 1)^{\frac{p - 3}2} * (p - 1) \equiv p - 1 \pmod p$
然后就可以从第二种写法变成第三种写法啦 !!(愉快结束)
orz%%%
orz%%%
orz%%%
orz %%%