中国剩余定理&Lucas定理&按位与—

链接：

hdu 5446

http://acm.hdu.edu.cn/showproblem.php?pid=5446

题意：

给你三个数$n, m, k$

第二行是$k$个数，$p_1,p_2,p_3 \cdots p_k$

所有$p$的值不相同且p都是质数

求$C(n, m) \ \%\ (p_1*p_2*p_3* \cdots *p_k)$的值

范围：$1\leq m\leq n\leq 1e18,\ 1\leq k\leq 10,p_i\leq 1e5$，保证$p_1*p_2*p_3* \cdots *p_k \leq 1e18$

分析：

我们知道题目要求$C(n, m) \ \% \ (p_1*p_2*p_3* \cdots *p_k)$的值

其实这个就是中国剩余定理最后算出结果后的最后一步求余

那$C(n, m)$相当于以前我们需要用中国剩余定理求的值

然而$C(n, m)$太大，我们只好先算出$C(n,m) \ \% \ p_1 = r_1 \\ C(n,m) \ \% \ p_2 = r_2 \\ C(n,m) \ \% \ ; p_3 = r_3 \\ \vdots \\ C(n,m) \ \% \ p_k = r_k \\$

用$Lucas$，这些$r_1,r_2,r_3 \cdots r_k$可以算出来，然后又是用中国剩余定理求答案。

注意，有些地方直接乘会爆long long，按位乘可避免。

AC代码：

#include<cstdio>

#include<cstring>

#include<cmath>

#include<iostream>

using namespace std;;

typedef long long LL;

void gcd(LL a, LL b, LL &d, LL &x, LL &y)

{

    if (!b) { d = a; x = ; y = ; }

    else { gcd(b, a % b, d, y, x); y -= x * (a / b); }

}

LL quickmul(LL m, LL n, LL k)

{

    m = (m % k + k) % k; n = (n % k + k) % k;   //变成较小的正数

    LL res = ;

    while (n > )

    {

        if (n & )

            res = (res + m) % k;

        m = (m + m) % k;

        n = n >> ;

    }

    return res;

}

//计算模n下a的逆。如果不存在逆，返回-1

//ax=1(mod n)

LL inv(LL a, LL n)

{

    LL d, x, y;

    gcd(a, n, d, x, y);

    return d ==  ? (x + n) % n : -;

}

//n! % p

LL fact(LL n, LL p)

{

    LL ret = ;

    for (int i = ; i <= n; i++)  ret = ret * i % p;

    return ret;

}

LL comp(LL n, LL m, LL p)

{

    if (n <  || m > n)  return ;

    return fact(n, p) * inv(fact(m, p), p) % p * inv(fact(n - m, p), p) % p;

}

LL lucas(LL a, LL b, LL m)

{

    LL ans = ;

    while (a && b)

    {

        ans = quickmul(ans, comp(a % m, b % m, m), m) % m;

        a /= m; b /= m;

    }

    return ans;

}

//n个方程：x=a[i](mod m[i])

LL china(int n, LL* a, LL* m)

{

    LL M = , d, y, x = ;

    for (int i = ; i < n; i++)  M *= m[i];

    for (int i = ; i < n; i++)

    {

        LL w = M / m[i];

        gcd(m[i], w, d, d, y);

        x = (x + quickmul(quickmul(w,y, M),a[i],M)) % M;   //直接乘会爆long long，要用按位乘

    }

    return (x + M) % M;

}

int k;

LL n, m;

LL p[ + ],r[ + ];

int main()

{

    int T;

    scanf("%d", &T);

    while (T--)

    {

        cin >> n >> m >> k;

        for (int i = ; i < k; i++)

            cin >> p[i];

        for (int i = ; i < k; i++)

            r[i] = lucas(n, m, p[i]);

        LL ans = china(k, r, p);

        cout << ans << endl;

    }

    return ;

}

参考链接：https://www.cnblogs.com/linyujun/p/5199684.html

巴特西

中国剩余定理&Lucas定理&按位与——hdu 5446

链接：

题意：

分析：

AC代码：

最新文章

热门文章