1004 Fansblog (HDU - 6608)

题意：

给定一个大素数 $P$P( $1e9\le P\le 1e14$1e9≤P≤1e14)，求最大的小于 $P$P的 $Q$Q,其中 $Q$Q也是素数，输出 $Q!modP$Q!modP。

思路：

$Q!modP=\frac{Q!\times (Q+1)\times (Q+2)\times ...(P-1)}{(Q+1)\times (Q+2)\times ...(P-1)}modP$Q!modP=(Q+1)×(Q+2)×...(P−1)Q!×(Q+1)×(Q+2)×...(P−1)​modP
$=\frac{Q!\times (Q+1)\times (Q+2)\times ...(P-1)}{(Q+1)\times (Q+2)\times ...(P-1)}modP$=(Q+1)×(Q+2)×...(P−1)Q!×(Q+1)×(Q+2)×...(P−1)​modP
$=\frac{(P-1)!}{(Q+1)\times (Q+2)\times ...(P-1)}modP$=(Q+1)×(Q+2)×...(P−1)(P−1)!​modP

$\because 威尔逊定理:若P为素数，则(P-1)!\equiv -1\left(modP\right)$∵威尔逊定理:若P为素数，则(P−1)!≡−1(modP)(其中n!表示n的阶乘)
威尔逊定理的逆定理也成立
$\therefore (P-1)!+1一定是P的倍数$∴(P−1)!+1一定是P的倍数
$\therefore (P-1)!modP==(P-1)$∴(P−1)!modP==(P−1)
$\therefore Q!modP=\frac{P-1}{(Q+1)\times (Q+2)\times ...(P-1)}modP$∴Q!modP=(Q+1)×(Q+2)×...(P−1)P−1​modP
从上面我们不难看出，只需要找到这个Q答案就出来了，那么问题来了Q咋找呢？暴力吗？对就是暴力：由于每个素数之前的距离不会太大，所以可以P–然后判断素数即可，那么还有个问题就是判断素数用什么呢？群友直接暴力sqrt判断也过了我却tle这里涉及到一个Miller-Rabin素数测试：快速判断一个数是不是素数
ps:p–遍历的时候开始用ans记录分母，因为涉及到除法取摸，所以用到乘法逆元，费马小定理： $a^{p-1}\equiv 1\left(modp\right)$ap−1≡1(modp)
$a^{p-2}\equiv inv\left(a\right)\left(modp\right)$ap−2≡inv(a)(modp)（这里a和p互质）

代码：

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define end '\n'
#define IOS ios::sync_with_stdio(0)
#include <iostream>

ll q_mul(ll a, ll b, ll mod) {
    ll ans = 0;
    a %= mod;
    while (b) {
        if (b & 1)
            ans = (ans + a) % mod;
        a = (a + a) % mod;
        b >>= 1;
    }
    return ans % mod;
}

ll pow_mod(ll a, ll b, ll n) {
    ll ans = 1,t = a % n;
    while (b) {
        if (b & 1)
            ans = q_mul(ans, t, n) % n;
        t = q_mul(t, t, n) % n;
        b = b >> 1;
    }
    return ans;
}

bool isprime(ll n) {
    ll pan[10] = {2, 3, 5, 7, 11, 31, 61, 73, 233, 331};
    ll i;
    for (i = 0; i < 10; i++)
        if (pow_mod(pan[i], n - 1, n) != 1)
            break;//if(pan[i]^(n-1)%n==1)this int is prime
    if (i == 10)
        return true;
    else
        return false;
}

int main() {
    ll ans, p;
    int t;
    while (~scanf("%d", &t)) {
        while (t--) {
            scanf("%lld", &p);
            ans = 1;
            for (ll i = p - 1; i > 0; i--) {
                if (isprime(i)) {
                    break;
                } else {
                    ans = q_mul(ans, i, p);
                }
            }
            ans = pow_mod(ans, p - 2, p);
            ans = q_mul(p-1,ans,p);
            printf("%lld\n", ans);
        }
    }
    return 0;
}