题目描述

一种非对称加密算法的密钥生成过程如下：

任选两个不同的质数p,q
计算N=pq，r=(p−1)(q−1)
选取小于r，且与r互质的整数e
计算整数d，使得 $ed \equiv 1 \pmod{r}$
二元组(N,e)称为公钥，二元组(N,d)称为私钥。

当需要加密消息n时，（假设n是一个小于N的整数，因为任何格式的消息都可转为整数表示），使用公钥(N,e)，按照 $n^e \equiv c \pmod{N}$ 运算，可得到密文c，对密文c解密时，用私钥(N,d)，按照 $c^d \equiv n \pmod{N}$ 运算，可得到原文n。算法正确性证明省略。
由于用公钥加密的密文仅能用对应的私钥解密，而不能用公钥解密，因此称为非对称加密算法。通常情况下，公钥由消息的接收方公开，而私钥由消息的接收方自己持有。这样任何发送消息的人都可以用公钥对消息加密，而只有消息的接收方自己能够解密消息。
现在，你的任务是寻找一种可行的方法来破解这种加密算法，即根据公钥破解出私钥，并据此解密密文。

输入输出格式

输入格式：
输入文件内容只有一行，为空格分隔的三个正整数e,N,c。

输出格式：
输出文件内容只有一行，为空格分隔的两个整数d,n。

输入输出样例

输入样例#1：

3 187 45

输出样例#1：

107 12

说明

对于30%的数据， $e,N,c \leq 2^{20}$ ；
对于100%的数据， $e,N,c \leq 2^{62}$

题解

本题需要的数学姿势有：Miller-Rabin素性测试与Pollard’s rho算法 | KSkun’s Blog
我一看，N马上一个Pollard-Rho套上去分解因数。p和q都有了你还愁什么d，扩欧一发逆元就出来了。
这不是个板子裸题吗……

代码

// Code by KSkun, 2018/4
#include <cstdio>
#include <cstring>
#include <ctime>
#include <cstdlib>

#include <algorithm>

typedef long long LL;

inline LL myabs(LL x) {
    return x < 0 ? -x : x;
}

inline char fgc() {
    static char buf[100000], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF : *p1++;
}

inline LL readint() {
    register LL res = 0, neg = 1;
    char c = fgc();
    while(c < '0' || c > '9') {
        if(c == '-') neg = -1;
        c = fgc();
    }
    while(c >= '0' && c <= '9') {
        res = res * 10 + c - '0';
        c = fgc();
    }
    return res * neg;
}

inline LL mul(LL a, LL b, LL p) {
    a %= p; b %= p;
    LL res = 0;
    while(b) {
        if(b & 1) res += a;
        if(res >= p) res %= p;
        a <<= 1; b >>= 1;
        if(a >= p) a %= p;
    }
    return res;
}

inline LL fpow(LL n, LL k, LL p) {
    LL res = 1; n %= p;
    for(; k; n = mul(n, n, p), k >>= 1) {
        if(k & 1) res = mul(res, n, p);
    }
    return res;
}

inline LL gcd(LL a, LL b) {
    if(a < b) std::swap(a, b);
    if(!b) return a;
    return gcd(b, a % b);
}

LL p, q;

inline LL pollard_rho(LL x, LL c) {
    LL xi = 1ll * rand() * rand() % (x - 1) + 1, y = xi, i = 1, k = 2;
    for(;;) {
        i++;
        xi = (mul(xi, xi, x) + c) % x;
        LL g = gcd(myabs(y - xi) % x, x);
        if(g > 1 && g < x) return g;
        if(xi == y) return x;
        if(i == k) {
            y = xi;
            k <<= 1;
        }
    }
    return x;
}

inline LL exgcd(LL a, LL b, LL &x, LL &y) {
    if(!b) {
        x = 1; y = 0; return a;
    }
    LL res = exgcd(b, a % b, x, y);
    LL t = x; x = y; y = t - a / b * y;
    return res;
}

LL e, N, c;

int main() {
    srand(time(NULL));
    e = readint(); N = readint(); c = readint();
    LL p = N;
    while(p >= N) p = pollard_rho(N, 1ll * rand() * rand() % (N - 1) + 1);
    LL r = (p - 1) * (N / p - 1);
    LL d, y;
    exgcd(e, r, d, y);
    d = (d % r + r) % r;
    LL n = fpow(c, d, N);
    printf("%lld %lld", d, n);
    return 0;
}

题解, 算法, 省选

by KSkun

0 Comments

2018年4月13日

Miller-Rabin素性测试与Pollard’s rho算法

Miller-Rabin素性测试（Miller–Rabin primality test） …

算法, 知识, Slider

by KSkun

0 Comments

2018年4月12日

[SDOI2013]随机数生成器题解

题目地址：洛谷：【P3306】[SDOI2013]随机数生成器 – 洛谷、BZ …

题解, 省选, 算法

by KSkun

0 Comments

2018年4月12日

BSGS算法（大步小步法）及其扩展原理及应用

BSGS算法（Baby-step giant-step）

算法用于解决解高次同余方程的问题，问题形式如：有同余方程 $a^x \equiv b \pmod{p}$ ，p为质数，求最小非负整数解x使得原方程成立。该算法的复杂度可以达到 $O(\sqrt{n} \log n)$ 甚至更低。

原理

根据欧拉定理，我们知道模的剩余类有产生循环的情况，即 $a^0, a^1, \ldots, a^{n-1}$ 模n（质数）意义下的剩余类与 $a^n, a^{n+1}, \ldots, a^{2n-1}$ 的剩余类相同，因此我们要的答案一定在 $[0, n-1]$ 内。
我们考虑先求出一部分a的幂次模p意义下的值，将它们存起来，然后使得剩下没有求值的部分能够想个办法利用已求值直接查出来。我们想起了根号，不如直接令求值的长度为 $m=\lceil \sqrt{p} \rceil$ 。
下面要考虑的是没有求值部分怎么来求，比如 $a^m, \ldots, a^{2m-1}$ 这一段，如果有解，一定是 $a^i \cdot a^m \equiv b \pmod{p}$ 的情况，我们把那个 $a^m$ 移到右边来，就变成了 $a^i \equiv b' \pmod{p}$ 且 $b' = ba^{-m}$ 。既然这样，我们为什么不考虑直接查这个 $b'$ 有没有对应的i的答案。这样，没有求值的部分的每一段就可以只进行一次查询来判断该段内是否有解。
这个保存，我们可以用一个map<int, int>来存，x[i]为余数为i的 $a^x$ 中最小的x值，则插入查询都为 $O(\log n)$ ，总复杂度达到 $O(\sqrt{n} \log n)$ 。当然还可以用HashMap存，复杂度会更优一些。

代码

本代码可以通过2417 — Discrete Logging一题。

STL map版本

// Code by KSkun, 2018/4
#include <cstdio>
#include <cmath>

#include <map>

typedef long long LL;

inline LL fpow(LL n, LL k, LL p) {
    LL res = 1; n %= p;
    while(k) {
        if(k & 1) res = res * n % p;
        n = n * n % p;
        k >>= 1;
    }
    return res;
}

std::map<LL, LL> x;

inline LL bsgs(LL a, LL b, LL p) {
    a %= p; b %= p;
    if(a == 0) return b == 0 ? 1 : -1;
    if(b == 1) return 0;
    LL m = ceil(sqrt(p - 1)), inv = fpow(a, p - m - 1, p);
    x.clear();
    x[1] = m; // use m instead of 0
    for(LL i = 1, e = 1; i < m; i++) {
        e = e * a % p;
        if(!x[e]) x[e] = i;
    }
    for(LL i = 0; i < m; i++) {
        if(x[b]) {
            LL res = x[b];
            return i * m + (res == m ? 0 : res);
        }
        b = b * inv % p;
    }
    return -1;
}

LL p, b, n;

int main() {
    while(scanf("%lld%lld%lld", &p, &b, &n) != EOF) {
        LL res = bsgs(b, n, p);
        if(res != -1) printf("%lld\n", res); else puts("no solution");
    }
    return 0;
}

HashMap版本

// Code by KSkun, 2018/4
#include <cstdio>
#include <cmath>
#include <cstring>

#include <algorithm>

typedef long long LL;

inline LL fpow(LL n, LL k, LL p) {
    LL res = 1; n %= p;
    while(k) {
        if(k & 1) res = res * n % p;
        n = n * n % p;
        k >>= 1;
    }
    return res;
}

const int MO = 611977, MAXN = 1000005;

struct HashMap {
    int head[MO + 5], key[MAXN], value[MAXN], nxt[MAXN], tot;
    inline void clear() {
        tot = 0;
        memset(head, -1, sizeof(head));
    }
    HashMap() {
        clear();
    }
    inline void insert(int k, int v) {
        int idx = k % MO;
        for(int i = head[idx]; ~i; i = nxt[i]) {
            if(key[i] == k) {
                value[i] = v;
                return;
            }
        }
        key[tot] = k; value[tot] = v; nxt[tot] = head[idx]; head[idx] = tot++;
    }
    inline int operator[](const int &k) const {
        int idx = k % MO;
        for(int i = head[idx]; ~i; i = nxt[i]) {
            if(key[i] == k) return value[i];
        }
        return -1;
    }
} x;

inline LL bsgs(LL a, LL b, LL p) {
    a %= p; b %= p;
    if(a == 0) return b == 0 ? 1 : -1;
    if(b == 1) return 0;
    LL m = ceil(sqrt(p - 1)), inv = fpow(a, p - m - 1, p);
    x.clear();
    x.insert(1, 0);
    for(LL i = 1, e = 1; i < m; i++) {
        e = e * a % p;
        if(x[e] == -1) x.insert(e, i);
    }
    for(LL i = 0; i < m; i++) {
        if(x[b] != -1) {
            LL res = x[b];
            return i * m + res;
        }
        b = b * inv % p;
    }
    return -1;
}

LL p, b, n;

int main() {
    while(scanf("%lld%lld%lld", &p, &b, &n) != EOF) {
        LL res = bsgs(b, n, p);
        if(res != -1) printf("%lld\n", res); else puts("no solution");
    }
    return 0;
}

扩展BSGS算法（exBSGS）

原理

咦，那p非质数怎么办呢？并不是说p-1以内没有答案，而是p可能会很大，根号的复杂度受不了啊！
想个办法来缩小p的范围。
我们想起了一些同余性质，比如 $a \equiv b \pmod{m} \Leftrightarrow \frac{a}{d} \equiv \frac{b}{d} \pmod{\frac{m}{d}}$ ，其中d为a、b、m的正公因数。我们想办法如此提公因数。
从方程左边拆一个a出来，提公因数，提完了就变成这样一个式子 $a^{x-1} \cdot \frac{a}{d} \equiv \frac{b}{d} \pmod{\frac{p}{d}}$ 。直到某个时候 $\mathrm{gcd}(a, \frac{p}{\prod_i d_i}) = 1$ 。
如果在提公因数的过程中，遇到 $\mathrm{gcd}(a, \frac{p}{\prod_i d_i}) \neq 1$ 且d不能整除b的情况，说明式子无解。因为 $a^x, p$ 中的一个共同的因数b中没有，显然不存在这样的b。
结束以后，我们得到的会是一个这样的式子
$a^{x-k} \cdot \frac{a^k}{\prod_i d_i} \equiv \frac{b}{\prod_i d_i} \pmod{\frac{p}{\prod_i d_i}}$
把分母搞掉
$a^x \equiv b \pmod{\frac{p}{\prod_i d_i}}$
这个直接扔给普通BSGS做就好了。

代码

本代码可以通过3243 — Clever Y一题。

STL map版（会TLE）

// Code by KSkun, 2018/4
#include <cstdio>
#include <cmath>

#include <map>

typedef long long LL;

inline char fgc() {
    static char buf[100000], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF : *p1++;
}

inline LL readint() {
    register LL res = 0, neg = 1;
    char c = fgc();
    while(c < '0' || c > '9') {
        if(c == '-') neg = -1;
        c = fgc();
    }
    while(c >= '0' && c <= '9') {
        res = res * 10 + c - '0';
        c = fgc();
    }
    return res * neg;
}

inline LL fpow(LL n, LL k, LL p) {
    LL res = 1; n %= p;
    while(k) {
        if(k & 1) res = res * n % p;
        n = n * n % p;
        k >>= 1;
    }
    return res;
}

inline LL exgcd(LL a, LL b, LL &x, LL &y) {
    if(!b) {
        x = 1; y = 0;
        return a;
    }
    LL res = exgcd(b, a % b, x, y);
    LL t = x; x = y; y = t - a / b * y;
    return res;
}

std::map<LL, LL> x;

inline LL bsgs(LL a, LL b, LL p) {
    a %= p; b %= p;
    if(a == 0) return b == 0 ? 1 : -1;
    if(b == 1) return 0;
    LL m = ceil(sqrt(p - 1)), inv, y;
    exgcd(fpow(a, m, p), p, inv, y); inv = (inv % p + p) % p;
    x.clear();
    x[1] = m; // use m instead of 0
    for(LL i = 1, e = 1; i < m; i++) {
        e = e * a % p;
        if(!x[e]) x[e] = i;
    }
    for(LL i = 0; i < m; i++) {
        if(x[b]) {
            LL res = x[b];
            return i * m + (res == m ? 0 : res);
        }
        b = b * inv % p;
    }
    return -1;
}

inline LL gcd(LL a, LL b) {
    if(!b) return a;
    return gcd(b, a % b);
}

inline LL exbsgs(LL a, LL b, LL p) {
    if(b == 1) return 0;
    LL tb = b, tmp = 1, k = 0;
    for(int g = gcd(a, p); g != 1; g = gcd(a, p)) {
        if(tb % g) return -1;
        tb /= g; p /= g; tmp = tmp * a / g % p;
        k++;
        if(tmp == tb) return k;
    }
    return bsgs(a, b, p);
}

LL a, b, p;

int main() {
    for(;;) {
        a = readint(); p = readint(); b = readint();
        if(!a && !b && !p) break;
        LL res = exbsgs(a, b, p);
        if(res != -1) printf("%lld\n", res); else puts("No Solution");
    }
    return 0;
}

HashMap版

// Code by KSkun, 2018/4
#include <cstdio>
#include <cmath>
#include <cstring>

#include <algorithm>

typedef long long LL;

inline char fgc() {
    static char buf[100000], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF 
        : *p1++;
}

inline LL readint() {
    register LL res = 0, neg = 1;
    char c = fgc();
    while(c < '0' || c > '9') {
        if(c == '-') neg = -1;
        c = fgc();
    }
    while(c >= '0' && c <= '9') {
        res = res * 10 + c - '0';
        c = fgc();
    }
    return res * neg;
}

inline LL fpow(LL n, LL k, LL p) {
    LL res = 1; n %= p;
    while(k) {
        if(k & 1) res = res * n % p;
        n = n * n % p;
        k >>= 1;
    }
    return res;
}

inline LL exgcd(LL a, LL b, LL &x, LL &y) {
    if(!b) {
        x = 1; y = 0;
        return a;
    }
    LL res = exgcd(b, a % b, x, y);
    LL t = x; x = y; y = t - a / b * y;
    return res;
}

const int MO = 611977, MAXN = 1000005;

struct HashMap {
    LL head[MO + 5], key[MAXN], value[MAXN], nxt[MAXN], tot;
    inline void clear() {
        tot = 0;
        memset(head, -1, sizeof(head));
    }
    HashMap() {
        clear();
    }
    inline void insert(LL k, LL v) {
        int idx = k % MO;
        for(int i = head[idx]; ~i; i = nxt[i]) {
            if(key[i] == k) {
                value[i] = std::min(value[i], v);
                return;
            }
        }
        key[tot] = k; value[tot] = v; nxt[tot] = head[idx]; head[idx] = tot++;
    }
    inline LL operator[](const LL &k) const {
        int idx = k % MO;
        for(int i = head[idx]; ~i; i = nxt[i]) {
            if(key[i] == k) return value[i];
        }
        return -1;
    }
} x;

inline LL bsgs(LL a, LL b, LL p) {
    a %= p; b %= p;
    if(a == 0) return b == 0 ? 1 : -1;
    if(b == 1) return 0;
    LL m = ceil(sqrt(p - 1)), inv, y;
    exgcd(fpow(a, m, p), p, inv, y); inv = (inv % p + p) % p;
    x.clear();
    x.insert(1, 0);
    for(LL i = 1, e = 1; i < m; i++) {
        e = e * a % p;
        if(x[e] == -1) x.insert(e, i);
    }
    for(LL i = 0; i < m; i++) {
        if(x[b] != -1) {
            LL res = x[b];
            return i * m + res;
        }
        b = b * inv % p;
    }
    return -1;
}

inline LL gcd(LL a, LL b) {
    if(!b) return a;
    return gcd(b, a % b);
}

inline LL exbsgs(LL a, LL b, LL p) {
    if(b == 1) return 0;
    LL tb = b, tmp = 1, k = 0;
    for(int g = gcd(a, p); g != 1; g = gcd(a, p)) {
        if(tb % g) return -1;
        tb /= g; p /= g; tmp = tmp * a / g % p;
        k++;
        if(tmp == tb) return k;
    }
    return bsgs(a, b, p);
}

LL a, b, p;

int main() {
    for(;;) {
        a = readint(); p = readint(); b = readint();
        if(!a && !b && !p) break;
        LL res = exbsgs(a, b, p);
        if(res != -1) printf("%lld\n", res); else puts("No Solution");
    }
    return 0;
}

参考资料

《算法竞赛入门经典训练指南》，刘汝佳，陈锋著，清华大学出版社，9787302291077
扩展BSGS算法 – TRTTG – 博客园

算法, 知识, Slider

by KSkun

2 Comments

2018年4月12日

散列表（HashMap）原理与实现

概述散列表（又称哈希表，Hash Table）是一种常用数据结构。它按照哈希特征分类存放 …

算法, 知识, Slider

by KSkun

0 Comments

2018年4月11日

中国剩余定理及其扩展原理及应用

中国剩余定理（Chinese remainder theorem）内容对于以下一元线性 …

算法, 知识, Slider

by KSkun

0 Comments

2018年4月10日

[国家集训队]礼物题解

题目地址：洛谷：【P2183】[国家集训队]礼物 – 洛谷、BZOJ：Problem 2142. — 礼物

题目描述

一年一度的圣诞节快要来到了。每年的圣诞节小E都会收到许多礼物，当然他也会送出许多礼物。不同的人物在小E心目中的重要性不同，在小E心中分量越重的人，收到的礼物会越多。小E从商店中购买了n件礼物，打算送给m个人，其中送给第i个人礼物数量为wi。请你帮忙计算出送礼物的方案数（两个方案被认为是不同的，当且仅当存在某个人在这两种方案中收到的礼物不同）。由于方案数可能会很大，你只需要输出模P后的结果。

输入输出格式

输入格式：
输入的第一行包含一个正整数P，表示模；
第二行包含两个整整数n和m，分别表示小E从商店购买的礼物数和接受礼物的人数；
以下m行每行仅包含一个正整数wi，表示小E要送给第i个人的礼物数量。

输出格式：
若不存在可行方案，则输出“Impossible”，否则输出一个整数，表示模P后的方案数。

输入输出样例

输入样例#1：

输出样例#1：

输入样例#2：

输出样例#2：

Impossible

说明

【样例说明】
下面是对样例1的说明。
以“/”分割，“/”前后分别表示送给第一个人和第二个人的礼物编号。12种方案详情如下：
1/23 1/24 1/34
2/13 2/14 2/34
3/12 3/14 3/24
4/12 4/13 4/23
设P=p1^c1 * p2^c2 * p3^c3 * … * pt ^ ct，pi为质数。
对于15%的数据，n≤15，m≤5，pi^ci≤10^5；
在剩下的85%数据中，约有60%的数据满足t≤2，ci=1，pi≤10^5，约有30%的数据满足pi≤200。
对于100%的数据，1≤n≤10^9，1≤m≤5，1≤pi^ci≤10^5，1≤P≤10^9。

题解

本题需要的数学姿势有：数学笔记：数论（Lucas、CRT） | KSkun’s Blog
参考资料：题解 P2183 【[国家集训队]礼物】 – 没名字可被用的博客 – 洛谷博客
无解仅当 $\sum_{i=1}^m w_i < n$ 。
有解的情况下，要求的就是 $\mathrm{C}_n^{w_1} \times \mathrm{C}_{n-w_1}^{w_2} \times \cdots \bmod P$ ，对于每个组合数，应用扩展Lucas定理求解即可。

代码

// Code by KSkun, 2018/4
#include <cstdio>

typedef long long LL;

struct Num {
    LL num, pcnt; // pcnt: p因子数量，num: 提取p因子后乘起来的积
    Num(LL num = 0, LL pcnt = 0): num(num), pcnt(pcnt) {}
};

inline char fgc() {
    static char buf[100000], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF 
        : *p1++;
}

inline LL readint() {
    register LL res = 0, neg = 1;
    char c = fgc();
    while(c < '0' || c > '9') {
        if(c == '-') neg = -1;
        c = fgc();
    }
    while(c >= '0' && c <= '9') {
        res = res * 10 + c - '0';
        c = fgc();
    }
    return res * neg;
}

const int MAXN = 100005, MAXM = 10;
const LL INF = 1e15;

inline LL fpow(LL n, LL k, LL p) {
    LL res = 1; n %= p;
    while(k) {
        if(k & 1) res = res * n % p;
        n = n * n % p;
        k >>= 1;
    }
    return res;
}

LL P, n, m, w[MAXM];

// calculate prime divisors in x
LL divi[MAXN], dcnt[MAXN], dpow[MAXN], dtot;

inline void calDivisor(LL x) {
    dtot = 0;
    for(LL i = 2; i * i <= P; i++) {
        if(x % i == 0) {
            divi[++dtot] = i;
            while(x % i == 0) {
                x /= i; dcnt[dtot]++;
            }
            dpow[dtot] = fpow(i, dcnt[dtot], INF);
        }
    }
    if(x != 1) {
        dtot++; 
        divi[dtot] = dpow[dtot] = x; dcnt[dtot] = 1;
    }
}

// calculate x! mod p^k
inline Num calFactorial(LL x, LL id) {
    if(x == 1 || x == 0) return Num(1, 0); // 1! = 0! = 1
    LL pk = dpow[id], res = 1;
    LL pnum = 0;
    for(LL i = x; i; i /= divi[id]) pnum += i / divi[id]; // 计算p因子的数量
    Num nxt = calFactorial(x / divi[id], id); // 递归计算提取了一个p因子的p倍数组成的阶乘
    res = res * nxt.num % pk; // 合并答案
    if(x >= pk) { // 如果有多段超过p^k的，预处理应用快速幂
        LL fac = 1;
        for(LL i = 1; i < pk; i++) {
            if(i % divi[id] == 0) continue;
            fac = fac * i % pk;
        }
        res = res * fpow(fac, x / pk, pk) % pk;
    }
    for(LL i = x; i >= 1; i--) { // 非整段p^k，暴力求解
        if(i % pk == 0) break;
        if(i % divi[id] == 0) continue;
        res = res * i % pk;
    }
    return Num(res, pnum);
}

inline LL exgcd(LL a, LL b, LL &x, LL &y) {
    if(!b) {
        x = 1; y = 0; return a;
    }
    LL res = exgcd(b, a % b, x, y);
    LL t = x; x = y; y = t - a / b * y;
    return res;
}

inline LL calInverse(LL n, LL p) {
    LL x, y;
    exgcd(n, p, x, y);
    return (x % p + p) % p;
}

LL crtm[MAXN];

// CRT求解组合数
inline LL crt() {
    LL res = 0;
    for(int i = 1; i <= dtot; i++) {
        res = (res + crtm[i] * P / dpow[i] % P * calInverse(P / dpow[i], dpow[i]) % P) % P;
    }
    return res;
}

int main() {
    P = readint(); n = readint(); m = readint();
    LL wsum = 0;
    for(int i = 1; i <= m; i++) {
        w[i] = readint();
        wsum += w[i];
    }
    if(wsum > n) {
        puts("Impossible"); return 0;
    }
    calDivisor(P);
    LL ans = 1;
    for(int i = 1; i <= m; i++) {
        for(int j = 1; j <= dtot; j++) {
            Num N = calFactorial(n, j), 
                M = calFactorial(w[i], j), 
                NM = calFactorial(n - w[i], j);
            // 分别代表n!、m!、(n-m)!
            N.pcnt -= M.pcnt + NM.pcnt;
            if(N.pcnt >= dcnt[j]) { // 如果p因子更多，说明能整除，模意义下为0
                crtm[j] = 0;
            } else {
                crtm[j] = N.num * calInverse(M.num, dpow[j]) % dpow[j] 
                    * calInverse(NM.num, dpow[j]) % dpow[j] 
                    * fpow(divi[j], N.pcnt, dpow[j]) % dpow[j]; // 把p因子乘进去
            }
        }
        ans = ans * crt() % P;
        n -= w[i];
    }
    printf("%lld", ans);
    return 0;
}

题解, 算法, NOI系列

by KSkun

0 Comments

2018年4月8日

HBOI2018游记

谨以此文献与我的OI生涯。 4月5日这天早上7点的动车，头天晚上调题睡得很晚于是就睡眠不 …

算法, 日常, 随笔

by KSkun

3 Comments

KSkun's Blog

最新文章

反演（莫比乌斯反演、二项式反演）原理及应用

[BZOJ4802]欧拉函数题解

[CQOI2016]密钥破解题解

题目描述

输入输出格式

输入输出样例

说明

题解

代码

Miller-Rabin素性测试与Pollard’s rho算法

[SDOI2013]随机数生成器题解

BSGS算法（大步小步法）及其扩展原理及应用

BSGS算法（Baby-step giant-step）

原理

代码

STL map版本

HashMap版本

扩展BSGS算法（exBSGS）

原理

代码

STL map版（会TLE）

HashMap版

参考资料

散列表（HashMap）原理与实现

中国剩余定理及其扩展原理及应用

[国家集训队]礼物题解

题目描述

输入输出格式

输入输出样例

说明

题解

代码

HBOI2018游记