Ceizenpok’s Formula

题目描述

Dr. Ceizenp’ok from planet i1c5l became famous across the whole Universe thanks to his recent discovery – the Ceizenpok’s formula. This formula has only three arguments: $n, k$ and $m$, and its value is a number of $k$-combinations of a set of $n$ modulo $m$.
While the whole Universe is trying to guess what the formula is useful for, we need to automate its calculation.

题意概述

求${n \choose k} \bmod m$。
数据范围:$1 \le n \le 10^{18}, \; 0 \le k \le n, \; 2 \le m \le 10^6$。

算法分析


$$
x={n \choose k}, \; m=p_1^{a_1}p_2^{a_2} \cdots p_q^{a_q}
$$
可以列出方程组
$$
\left\{
\begin{array}{c}
x \equiv r_1 \pmod{p_1^{a_1}} \\
x \equiv r_2 \pmod{p_2^{a_2}} \\
\cdots \\
x \equiv r_q \pmod{p_q^{a_q}}
\end{array}
\right.
$$
由于模数两两互质,所以该方程组在模$m$意义下有唯一解。
考虑如何求$r_i$。实际上,我们要求的就是${n \choose k} \bmod p_i^{a_i}$。我们知道
$$
{n \choose k}={n! \over k!(n-k)!}
$$
那么只要求出$n! \bmod p_i^{a_i}, \; k! \bmod p_i^{a_i}, \; (n-k)! \bmod p_i^{a_i}$的值,就可以用逆元求出${n \choose k} \bmod p_i^{a_i}$。
对于如何求$n! \bmod p_i^{a_i}$,令
$$
f(n)=n! \bmod p_i^{a_i}
$$
由$x \equiv x+p_i^{a_i} \pmod{p_i^{a_i}}$,可得
$$
f(n)=\left(f\left(\left\lfloor{n \over p_i}\right\rfloor\right)\cdot p_i^{\lfloor n/p_i \rfloor}\cdot\left(\prod_{i \in [1, p_i^{a_i}], \; p_i\not\mid i}i\right)^{\lfloor n/p_i^{a_i} \rfloor}\cdot\prod_{i \in [1, n \bmod p_i^{a_i}], \; p_i\not\mid i}i\right)\bmod p_i^{a_i}
$$
但是$k!, \; (n-k)!$在模$p_i^{a_i}$意义下可能不存在逆元,因此需要将$n!, \; k!, \; (n-k)!$中的$p_i$因子提取出来,求出逆元后再乘回去。
这样就得到了所有$r_i$。用中国剩余定理求解方程组即可。

代码

/*
 * Your lucky number has been disconnected.
 */

#include <algorithm>
#include <cstdio>
#include <cstring>

#define int long long

int power(int a, int b, int m) {
  int ret = 1;
  for (; b; b >>= 1)
    b & 1 && ((ret *= a) %= m), (a *= a) %= m;
  return ret;
}

void ex_gcd(int a, int b, int &x, int &y) {
  if (!b) {
    x = 1, y = 0;
    return;
  }
  ex_gcd(b, a % b, y, x), y -= a / b * x;
}

int get_inv(int a, int b) {
  int x, y;
  ex_gcd(a, b, x, y);
  return (x + b) % b;
}

int get_fac(int n, int p, int k) {
  int m = power(p, k, 1e9), ret = 1;
  for (; n; n /= p) {
    if (n / m) {
      int rec = 1;
      for (int i = 2; i < m; ++i)
        if (i % p)
          (rec *= i) %= m;
      (ret *= power(rec, n / m, m)) %= m;
    }
    for (int i = n % m; i > 1; --i)
      if (i % p)
        (ret *= i) %= m;
  }
  return ret;
}

int calc(int N, int K, int M, int p, int k) {
  int a = get_fac(N, p, k), b = get_fac(K, p, k), c = get_fac(N - K, p, k),
      cnt = 0;
  for (int i = N; i; i /= p)
    cnt += i / p;
  for (int i = K; i; i /= p)
    cnt -= i / p;
  for (int i = N - K; i; i /= p)
    cnt -= i / p;
  int m = power(p, k, 1e9),
      ret = a * get_inv(b, m) % m * get_inv(c, m) % m * power(p, cnt, m) % m;
  return ret * (M / m) % M * get_inv(M / m, m) % M;
}

signed main() {
  int N, K, M, ans = 0;
  scanf("%lld%lld%lld", &N, &K, &M);
  for (int i = 2, t = M; t > 1; ++i)
    if (!(t % i)) {
      int k = 0;
      for (; !(t % i); ++k, t /= i)
        ;
      (ans += calc(N, K, M, i, k)) %= M;
    }
  printf("%lld\n", ans);
  return 0;
}

Strange Way to Express Integers

题目描述

Elina is reading a book written by Rujia Liu, which introduces a strange way to express non-negative integers. The way is described as following:

  • Choose $k$ different positive integers $a_1, a_2, \ldots, a_k$. For some non-negative $m$, divide it by every $a_i$ to find the remainder $r_i$. If $a_1, a_2, \ldots, a_k$ are properly chosen, $m$ can be determined, then the pairs $(a_i, r_i)$ can be used to express $m$.

“It is easy to calculate the pairs from $m$,” said Elina. “But how can I find $m$ from the pairs?”
Since Elina is new to programming, this problem is too difficult for her. Can you help her?

题意概述

给定同余方程组
$$
\left\{
\begin{array}{c}
x \equiv r_1 \pmod{a_1} \\
x \equiv r_2 \pmod{a_2} \\
\cdots \\
x \equiv r_k \pmod{a_k}
\end{array}
\right.
$$
求$x$的最小非负整数解。
数据范围:所有输入输出均可以表示为64位整型。

算法分析

对于两个方程
$$
\begin{align}
x &\equiv r_1 \pmod{a_1} \\
x &\equiv r_2 \pmod{a_2}
\end{align}
$$
考虑将它们合并。易知
$$
x=r_1+k_1a_1=r_2+k_2a_2
$$
移项得
$$
k_1a_1=r_2-r_1+k_2a_2
$$
由贝祖定理可知,这个方程有整数解的充要条件为$(a_1, a_2) \mid r_2-r_1$。方程两边同时除以$(a_1, a_2)$
$$
\begin{align}
k_1{a_1 \over (a_1, a_2)}&={r_2-r_1 \over (a_1, a_2)}+k_2{a_2 \over (a_1, a_2)} \\
k_1{a_1 \over (a_1, a_2)} &\equiv {r_2-r_1 \over (a_1, a_2)} \pmod{{a_2 \over (a_1, a_2)}} \\
k_1 &\equiv \left( {a_1 \over (a_1, a_2)} \right)^{-1} \cdot {r_2-r_1 \over (a_1, a_2)} \pmod{{a_2 \over (a_1, a_2)}}
\end{align}
$$
将其代回$x=r_1+k_1a_1$,得
$$
x \equiv r_1+k_1a_1 \pmod{{a_1a_2 \over (a_1, a_2)}}
$$
至此已成功将两个方程合并为一个相同形式的方程。

代码

/*
 * Your life would be very empty if you had nothing to regret.
 */

#include <algorithm>
#include <cstdio>
#include <cstring>

#define int long long

int ex_gcd(int a, int b, int &x, int &y) {
  if (!b) {
    x = 1, y = 0;
    return a;
  }
  int ret = ex_gcd(b, a % b, y, x);
  y -= a / b * x;
  return ret;
}

int get_gcd(int a, int b) {
  int x, y;
  return ex_gcd(a, b, x, y);
}

int get_inv(int a, int b) {
  int x, y;
  return ex_gcd(a, b, x, y), (x += b) %= b;
}

signed main() {
  for (int k, a, r; ~scanf("%lld%lld%lld", &k, &a, &r);) {
    int flag = 0;
    for (int ai, ri; --k;) {
      scanf("%lld%lld", &ai, &ri);
      int gcd = get_gcd(a, ai);
      if ((r - ri) % gcd)
        flag = 1;
      r += get_inv(a / gcd, ai / gcd) * ((ri - r) / gcd) % (ai / gcd) * a;
      (a /= gcd) *= ai, ((r %= a) += a) %= a;
    }
    if (flag)
      puts("-1");
    else
      printf("%lld\n", r);
  }
  return 0;
}

Notes on Module

逆元

对于模意义下的除法,$a/x \equiv b \pmod m \Leftrightarrow a \times x^{-1} \equiv b \pmod m$,则称$x^{-1}$为$x$在模$m$意义下的逆元。
关于逆元的求法可以参考Notes on Multiplicative Inverse
考虑线性同余方程$ax \equiv b \pmod m$,有
$$(a/(a, m))x \equiv b/(a, m) \pmod {m/(a, m)}$$
显然,当$(a, m) \not \mid b$时,原方程无解;否则,有
$$x \equiv (a/(a, m))^{-1} \times (b/(a, m)) \pmod {m/(a, m)}$$
因此原方程的解为
$$x \equiv (a/(a, m))^{-1} \times (b/(a, m)) + (m/(a, m)) \times k \pmod m \; (0 \le k \lt (a, m))$$
原方程可能有多解,也可能无解。


费马小定理

当$p$是素数时,对任意整数$x$都有$x^p \equiv x \pmod p$。若$p \not \mid x$,则
$$
\begin{align}
x^{p-1} &\equiv 1 \pmod p \\
x^{-1} &\equiv x^{p-2} \pmod p
\end{align}
$$
当$m$不是素数且$x$与$m$互质时,有
$$x^{\varphi(m)} \equiv 1 \pmod m$$
其中$\varphi(m)$为欧拉函数,其值等于不大于$m$的正整数中与$m$互质的数的个数。
利用线性筛,每次发现质数$p$时把它倍数的欧拉函数乘上$(p-1)/p$,就可以求出$1$到$n$的欧拉函数。


线性同余方程组

给定由若干个形如$a_ix \equiv b_i \pmod {m_i}$的方程组成的方程组,求它的解。如果有解,则一定有无穷多解,并可以表示为$x \equiv b \pmod m$的形式,因此问题转化为求解$b$和$m$。如果我们能求解方程组
$$
\left\{
\begin{align}
x &\equiv b_i \pmod {m_i} \\
ax &\equiv b_{i+1} \pmod {m_{i+1}}
\end{align}
\right.
$$
那么只要对方程逐个求解即可得到答案。
因为$x \equiv b_i \pmod {m_i}$,所以$x=tm_i+b_i$,代入第二个式子,得到
$$a(tm_i+b_i) \equiv b_{i+1} \pmod {m_{i+1}}$$
移项后得到
$$atm_i \equiv b_{i+1}-ab_i \pmod {m_{i+1}}$$
这是一个一次同余方程。当$(am_i, m_{i+1}) \not \mid b_{i+1}-ab_i$时原方程组无解。


中国剩余定理

如果同余方程组满足
$$\forall i \in [1, n], \; a_i=1 \land \forall i, j \in [1, n] \land i \neq j, \; (m_i, m_j)=1$$
那么答案的形式一定是
$$x \equiv b \pmod {\prod m_i}$$
反之,对于一个合数$n$,如果$n=ab \land (a, b)=1$,那么$x \bmod n$的值确定了之后,$x \bmod a$和$x \bmod b$的值也就确定了。因此,以$n$为模数来考虑和以$a$、$b$为模数来考虑是等价的。这个定理叫做中国剩余定理。
所以,对于模合数的情况只要考虑模若干$p^k$($p$为素数)的情况就可以了。如果$n$是一个square-free的数,那么问题就转化成模素数的情况,从而变得容易求解。
若$n$不是square-free的数,可以将每个数字$x$用一个二元组$(a, b)$表示,代表$x=ap_i^b$。有以下运算规则
$$
\begin{align}
(a, b)\times(c, d)&=(ac, b+d) \\
(a, b)/(c, d)&=(ac^{-1}, b-d)
\end{align}
$$
关于扩展中国剩余定理可参考Strange Way to Express Integers


$n!$

在计数问题中经常用到$n!$。因此有必要了解$n!$在模$p$意义下的一些性质。
假设$p$是素数,$n!=ap^e \; (a \not \mid p)$,求$a \bmod p$和$e$,$e$是$n!$能够迭代整除$p$的次数。显然$$e=n/p+n/p^2+n/p^3+ \cdots$$
因为$n/d$等于不超过$n$的能被$d$整除的正整数个数。
接下来计算$a \bmod p$。可以发现,不能被$p$整除的项在模$p$意义下呈周期性,它们的积为
$$((p-1)!)^{n/p} \times (n \bmod p)!$$
事实上,根据威尔逊定理,$(p-1)! \equiv -1 \pmod p$。因为除了$1$和$p-1$之外的其余项都可以和各自的逆元相乘得到$1$。
接下来计算可以被$p$整除的项的积。可以被$p$整除的项为$p, 2p, 3p, \ldots, (n/p)p$,将$p$消去后得到$1, 2, 3, \ldots, n/p$。因此问题的范围就由$n$缩小到了$n/p$。


${n \choose k} \bmod p$

当$p$不太大时,根据卢卡斯定理,令
$$n=\sum n_ip^i \; (0 \le n_i \lt p), \; k=\sum k_ip^i \; (0 \le k_i \lt p)$$

$${n \choose k} \equiv \prod {n_i \choose k_i} \pmod p$$
还有另一种思路。首先,把${n \choose k}$写成阶乘的形式
$${n \choose k}={n! \over k!(n-k)!}$$

$$n!=a_1p^{e_1}, \; k!=a_2p^{e_2}, \; (n-k)!=a_3p^{e_3}$$
从中可以看出,当$e_1 \gt e_2+e_3$时,${n \choose k}$可以被$p$整除;当$e_1=e_2+e_3$时,${n \choose k}$无法被$p$整除,此时${n \choose k} \equiv a_1(a_2a_3)^{-1} \pmod p$。
关于扩展卢卡斯定理可参考Ceizenpok’s Formula