来自"NOCOW"

可以证明，f(n)=n!

证明如下：

已知，f(1)=1,f(2)=2,现在证明当1<=i<=n-1，有f(i)=i!时，f(n)=n!

因为f(n)=1 + f(1)g(1) + f(2)g(2) + … + f(n−1)g(n−1)

所以f(n)-f(n-1)化简：f(n)=f(n-1)+f(n-1)*g(n-1)....1式

类似的f(n-1)=f(n-2)+f(n-2)*g(n-2)....2式

有谁可以将这以下的证明过程写详细点,为什么f(n-1)=(n-1)! (by 路人甲） (re:这是归纳法证明。)

由f(n-1)=(n-1)! 和1式可得 f(n)=(n-1)!+(n-1)!g(n-1)....3式

由f(n-2)=(n-2)! 和2式可得 (n-1)!=(n-2)!+(n-2)!g(n-2)

因此 g(n-2)=((n-1)!-(n-2)!)/(n-2)!=n-2

类似，可得 g(n-3)=n-3

又因为g(n-1)=1 + 2g(1) + 2g(2) + 2g(3) + … + 2g(n−2) − g(n−2)g(n−2)

g(n-2)=1 + 2g(1) + 2g(2) + 2g(3) + … + 2g(n−3) − g(n−3)g(n−3)

所以 g(n-1)=3g(n-2)+g(n-3)g(n-3)-g(n-2)g(n-2)

=3(n-2)+(n-3)(n-3)-(n-2)(n-2)

=n-1

由g(n-1)=n-1 和3式可得 f(n)=(n-1)!+(n-1)!(n-1)=(1+n-1)(n-1)!=n!

我的程序：

var

   n,p,i:longint;
   w:int64;

begin

while n*p<>0 do
 begin
  w:=1;
  for i:=1 to n do
   w:=w*i mod p;
  writeln(w);
  readln(n,p);
 end;

end.