Bookmarks

You haven't yet saved any bookmarks. To bookmark a post, just click .

  • 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;
    }