每日算法——一道数学题

关键字

威尔逊定理

题目

给定 n，求 (n-1)!\%n 的值。

输入描述

第一行输入一个 n，

1 \leq n \leq 10^9

输出描述

输出一个整数，代表答案

示例

输入

9

输出

0

知识点 ¹

当且仅当 p 为质数时，(p-1)! \equiv -1(\mod p)

证明：

充分性：

如果 p 不是质数，当 p=4 时，显然 (p-1)! \equiv 6 \equiv 2 (\mod p)，当 p > 4 时，若 p 不是完全平方数，则存在两个并不等的因数 a, b 使得 ab=p，则 (p-1)! \equiv nab \equiv 0 (\mod p)；若 p 是完全平方数即 p = k ^2，因为 p>4，所以 k>2, (k, 2k) < p, (p-1)! \equiv n(k*2k) \equiv 2nk^2 \equiv 0(\mod p)

必要性：

若 p 是素数,取集合 A=\{1,2,3,...p -1\}; 则 A 构成模 p 乘法的简化剩余系,即任意 i \in A, 存在 j \in A，使得 (ij) \equiv 1(\mod p)，那么 A 中的元素是不是恰好两两配对呢？不一定，但只需考虑这种情况：

x^2 \equiv 1(\mod p)

解得：x \equiv 1 (\mod p) 或 x \equiv p-1(\mod p)

其余两两配对，故而

(p-1)! \equiv 1 \cdot (p-1) \equiv -1 (\mod p)

解决方案

    
#include <bits/stdc++.h>
using namespace std;
bool isPrime(int num){
    for (int i=2; i<= sqrt(num); i++){
        if (num % i == 0) return false;
    }
    return true;
}
int main(){
    int n;
    cin >> n;
    if (n == 4) cout << 2;
    else if (isPrime(n)) cout << n-1;
    else cout << 0;
    return 0;
}
    
    

引用资料