FansBlog - 2019 Multi-University Training Contest 1

题目

Farmer John keeps a website called ‘FansBlog’ .Everyday , there are many people visited this blog.One day, he find the visits has reached P , which is a prime number.He thinks it is a interesting fact.And he remembers that the visits had reached another prime number.He try to find out the largest prime number Q ( Q < P ) ,and get the answer of Q! Module P.But he is too busy to find out the answer. So he ask you for help. ( Q! is the product of all positive integers less than or equal to n: n! = n * (n-1) * (n-2) * (n-3) *… * 3 * 2 * 1 . For example, 4! = 4 * 3 * 2 * 1 = 24 )

输入

First line contains an number T(1<=T<=10) indicating the number of testcases.
Then T line follows, each contains a positive prime number P (1e9≤p≤1e14)

样例输入

1
1000000007

输出

For each testcase, output an integer representing the factorial of Q modulo P.

样例输出

328400734

题意

有一个质数P (1e9≤p≤1e14),要求找到比P小但是和P的差最小的质数Q，求Q! mod P.

题解

质数分布：任意2000个自然数以内一定存在质数。
因此对于[P-1,P-2001]的区间的每一个数，判断它是否是质数，一旦找到质数则为Q
然后用Wilson定理计算答案
注意计算过程的数据可能很大，需要__int128

Code

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

ll MOD;

ll power(ll x, unsigned long long y, ll p) {
    ll res = 1LL;
    x = x % p;
    while (y > 0) {
        if (y & 1LL)
            res = (res * x) % p;
        y = y >> 1LL;
        x = (x * x) % p;
    }
    return res;
}

ll prime[7] = {2, 325, 9375, 28178, 450775, 9780504, 1795265022};

ll qm(ll a, ll b, ll c) {
    long long ans = 0, res = a;
    while (b) {
        if (b & 1)
            ans = (ans + res) % c;
        res = (res + res) % c;
        b >>= 1;
    }
    return (ll)ans;
}
ll mul(ll a, ll b) { return (ll)(__int128(a) * b % MOD); }
ll qp(ll a, ll b, ll c) {
    ll ans = 1, res = a;
    while (b) {
        if (b & 1)
            ans = qm(ans, res, c);
        res = qm(res, res, c);
        b >>= 1;
    }
    return ans;
}
__int128 qp2(__int128 a, __int128 b, __int128 c) {
    __int128 ans = 1, res = a;
    while (b) {
        if (b & 1)
            ans = qm(ans, res, c);
        res = qm(res, res, c);
        b >>= 1;
    }
    return ans;
}
bool Miller_Rabin(ll x) {
    ll i, j, k;
    ll s = 0, t = x - 1;
    if (x == 2)
        return true;
    if (x < 2 || !(x & 1))
        return false;
    while (!(t & 1)) {
        s++;
        t >>= 1;
    }
    for (i = 0; i < 6 && prime[i] < x; ++i) {
        ll a = prime[i];
        ll b = qp(a, t, x);
        for (j = 1; j <= s; ++j) {
            k = qm(b, b, x);
            if (k == 1 && b != 1 && b != x - 1)
                return false;
            b = k;
        }
        if (b != 1)
            return false;
    }
    return true;
}

__int128 modInverse(__int128 a, __int128 p) { return qp(a, p - 2ll, p); }

ll modFact(ll n, ll p) {
    if (p <= n)
        return 0;
    __int128 res = (p - 1ll);
    for (__int128 i = n + 1ll; i < p; i++) {
        res = ((res % p) * (modInverse(i, p) % p)) % p;
    }
    return (ll)res;
}

int main() {
    ll t;
    scanf("%lld", &t);
    while (t-- > 0) {
        scanf("%lld", &MOD);
        ll i;
        for (i = MOD - 1; i > MOD - 2001; i--) {
            if (Miller_Rabin(i))
                break;
        }
        printf("%lld\n", modFact(i, MOD));
    }
    return 0;
}