BZOJ 1951: [SDOI2010]古代猪文 – [Lucas/CRT]


题目传送门(BZOJ)

题解 :

题意即求 :

P = \sum\limits_{k|N}C(N, k)\;\;\;\;\;G^P\mod 999911659

\because G^P\equiv G^{P\%\varphi(mod)}

mod是个质数, 所以\varphi(mod) = 999911658

所以关键变成了求\sum\limits_{k|N}C(N,k)\mod 999911658

发现如果能用lucas的话, 由于约数是不到\sqrt N级别的(在10^9范围内, 最多的一个不超过2000)

那么我们O(\sqrt N)分解约数, 再2000\times \log N lucas(由于约数不可能都到N级别, 实际会小).

然后999911658并不是一个质数, 999911658 = 2\times 3\times 4679\times 35617

我们对于这四个质因数分别求解, 再用CRT合并一下就可以了, 当然也可以同余方程求解

对于每个质因数pritmp=999911658\div pri,答案等于

(\sum\limits_{k|N}C(N,k)\mod pri) \times tmp\%999911658\times inv(tmp)

我们把每个质因数的答案加起来就是要求的P

代码 :

#include 
using namespace std;
#define ll long long
const ll p1 = 999911659, p2 = p1-1;
int num[4] = {2, 3, 4679, 35617};
int n, g;
ll fac[40000], sum[4];
inline ll quickpow(ll x, ll y, ll p) {
    ll res = 1;
    for(; y; y >>= 1, x = x*x%p) if(y&1) res = res*x%p;
    return res;
}
ll C(ll n, ll m, ll p) {
    if(n

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注