c - 值为20,10000，出现错误

Question

测试两个32位整数m，其阶乘为m!可以被n整除。如果可以，函数 divides() 返回 1，否则返回 0。如下面的代码，问题是当m = 2010000时，发生了错误。你能解释一下为什么吗？

#include <stdio.h>

long factorial(long n){
    if((n == 0) || (n == 1)) return 1;
    else{
    return (n * factorial(n-1));
    }        
}
int divides (long n,long m)
{
    long facN;
    printf("n=%ld ",n);
    facN = factorial(n);
    if(m != 0){
    if(facN == 1) return 0;
        else{
            if(facN % m == 0) return 1;
            else if((facN % m) != 0)return 0;
        }
   }
   else if(m == 0) return 0;
}

int main()
{
    printf("%d", divides(2000000,1));
}

Answer 1

您需要计算已考虑模数的阶乘。使用以下身份:

(a * b) % n = ((a % n) * (b % n)) % n

我们可以计算阶乘为:

m! % n = (((((1 % n) * 2) % n) * 3) % n) ...) % n