算法竞赛中的数学问题（二）

数学基础问题

Again Prime? No time.

• 对 $n!$ 进行阶乘分解，对某个素因子 $p$, 其分解为 $p^{\text{res}}$
• 对 $m$ 进行素因子分解，并且求出和阶乘素因子的交集

  $$\left(p^e\right)^k = \text{res} \quad ans \leftarrow \min \left\lfloor \frac{\text{res}}{e} \right\rfloor$$

  注意这里即使 $\text{res} < e$ 也没有关系，$\text{res} < e$ 意味着 $\left\lfloor \text{res}/e \right\rfloor = 0$
  $ans = 0, \ ans = \infty$ 均无解

The Super Powers
不妨设一个超级幂的唯一分解，对于某质因子 $p$ 有

$$\begin{aligned} p^e &= p^{s_1s_2\cdots s_m} \\ e &= s_1s_2\cdots s_m \end{aligned}$$

不难想到，如果一个数是超级幂，满足

$$\begin{cases} e \ \text{是合数，且} \ e > 4 \\ \text{枚举底数} \ x \in [2 \to 2^{64}-1], e \leqslant \left\lceil \frac{64 \cdot \log(2)}{\log(x)} \right\rceil - 1 \end{cases}$$

暴力法即可解决

• $\textbf{for} \ \forall x \in [2 \cdots ]$ 枚举底数 $x, \quad e \leqslant \left\lceil \frac{64 \cdot \log(2)}{\log(x)} \right\rceil - 1$
  $res \leftarrow 1 \quad \textbf{for} \ \forall i \in [1 \to e]$ 枚举指数 $i$
  $\quad res \leftarrow res \times \prod x \ \Leftrightarrow \ res = res \cdot x^i$
  $\textbf{if} \ i \ \text{为合数}, \quad x^{i} \ \text{是 super power}, \ res \to \text{ans}\{\cdots \}$
• 说明，在算法中我们只需要从小到大枚举底数 $x$，然后取幂指 $i$ 为合数即可，如果 $x$ 可以进行分解
  因为是从小到大枚举的，$x$ 的因数一定在 $x$ 之前被检查到了，并不会漏解

Teams
根据组合原理，所求的方案是

$$\begin{aligned} S(n) &= \sum_{k=1}^{n} \binom{n}{k} \binom{k}{1} = \sum_{k=1}^{n} k \cdot \binom{n}{k} \\ S(n) &= 1\binom{n}{1} + 2\binom{n}{2} + \cdots (n-1) \binom{n}{n-1} + n \binom{n}{n} \\ S(n) = n\binom{n}{n} + &(n-1)\binom{n}{n-1} + (n-2)\binom{n}{n-2} \cdots + 1\binom{n}{1} \end{aligned}$$

从而可以推出

$$2S(n) = n \cdot 2^{n} \Rightarrow S(n) = n \cdot 2^{n-1}$$

唯一分解定理

LCM Cardinality
其实条件可以写成

$$\begin{cases} &a \cdot b = n \cdot \text{gcd}(a, b) \\ &\text{gcd}(a, b) \mid n \end{cases}$$

很容易想到应该对 $n$ 进行素因子分解

• 对 $n$ 进行素因子分解

  $$\begin{aligned} n &= p_1^{s_1}p_2^{s_2} \cdots p_m^{s_m} \\ a &= p_1^{a_1}p_2^{a_2} \cdots p_m^{s_m} \\ b &= p_1^{b_1}p_2^{b_2} \cdots p_m^{s_m} \end{aligned}$$

• 原问题等价于

  $$\begin{cases} \max(a_i, b_i) = s_i \\ s_i \text{中有多少种无序} (a_i, b_i) 组合 \end{cases}$$

• 先从 $(a_i, b_i)$ 中任选一个令其等于 $s_i$，有 $2 \choose 1$ 种
  剩下的元素从 $[0, s_i-1]$ 中选，有 $s_i$ 种，一共有 $\binom{2}{1} \cdot s_i = 2s_i$ 种
  另外考虑到 $a_i = b_i = s_i$ 这一种情况，因为是 $(a_i, b_i)$ 无序数组，所以 $(s_i, s_i)$ 算作 $1$ 种
  $\forall \ p_i$，一共有 $2s_i + 1$ 种选择

• $$\frac{\prod_i (2s_i + 1)}{2}$$

  但注意 $\prod(2s_i + 1)$ 是奇数，此时 $\prod(2s_i+1)$ 的结果中包含 $(n, n)$ 这一组
  要 $+1$ 后除以 $2$ 才是答案

  $$ans = \left\lceil \frac{\prod_i (2s_i + 1) + 1}{2} \right\rceil = \left\lfloor \frac{\prod_i (2s_i+1)}{2} \right\rfloor + 1$$

UVA10791

• 先对 $n=\textbf{LCM}$ 进行素因子分解，$n = \prod p_i^{s_i}$
  那么 $\min \text{sum} = \sum p_i^{s_i}$，其实不难证明
  对于任意两个素因子 $p_i, p_j, \quad p_i < p_j$，显然有 $p_ip_j \leqslant p_i + p_j$

  $$p_ip_j \leqslant p_i + p_j \Rightarrow \frac{p_i+p_j}{p_ip_j} \leqslant 1 \Rightarrow \frac{1}{p_i} + \frac{1}{p_j} \leqslant 1$$

  由此 $\sum p_i^{s_i}$ 即为最小
• 在素因子分解后，如果少了某个素因子 $p_i$，那么 $\text{lcm}$ 就 $< n$ 了，如果多了某个素因子 $p_i$，如果此时 $\text{lcm}(A, B) = n$
  令 $B \leftarrow B/p_i$，仍然满足 $\text{lcm} = n$ 并且 $A+B$ 更小
• 另外，如果 $n$ 是素数或者是 $n=1$，直接返回 $n+1$ 即可

同余与剩余类

任意整数 $a \bmod p$，可以根据余数组成 $p$ 个类，分别为

$$\{0\}, \{1\}, \cdots , \{p-1\}$$

于是很多同余问题就转换成剩余类计数问题，比如我们可以用 $s_{\{0\}}$ 表示剩余类 $\{0\}$ 的个数
剩余类的个数表示为

$$s_{\{0\}}, s_{\{1\}}, \cdots , s_{\{p-1\}}$$

如果一个 $B$ 位数能够被 $p$ 整除，那么这个数每个数位的和 $\sum_{i}$ 也能够被 $p$ 整除
可以遍历每个数位 $\textbf{for} \ \forall i \in [0, B)$，统计出

$$\begin{gathered} s_{\{0\}}, s_{\{1\}}, \cdots , s_{\{p-1\}} \\ \sum_{i} \equiv 1s_{\{1\}} + 2s_{\{2\}} + \cdots + (p-1)s_{\{p-1\}} (\bmod p) \end{gathered}$$

UVA11489

• 对于数位 $b_i$，统计出剩余类个数 $s_{\{0\}}, s_{\{1\}}, s_{\{2\}}$，并且计算出

  $$\sum_{i} \equiv (s_{\{1\}} + 2s_{\{2\}}) (\bmod 3)$$

• 如果 $\sum_{i} \equiv 0 (\bmod 3)$，那么只需要考虑 $\{0\}$ 这个剩余类
  $s_{\{0\}} \bmod 2 = 1$，$S$ 获胜，否则 $T$ 获胜
• 如果$\sum_i \equiv \{1\} \ \textbf{or} \ \{2\}$，需要考虑 $\{1\}, \{2\}$ 这两个剩余类
  • 如果 $\sum_i \equiv \{1\}, \quad s_{\{1\}} > 0$，要满足取完数，所有数位的和能够被 $3$ 整除
    $S$ 第一次取一定是拿走 $b_i \equiv 1(\bmod 3)$ 的那个数位，这样
    $\sum \leftarrow (1-1) (\bmod 3) \Rightarrow \sum \equiv 0 (\bmod 3)$，才能使剩下的数合法
  • $\sum_i \equiv \{2\}$ 同理
  • 如果 $\sum_i \equiv m (\bmod 3), \quad s_{\{m\}} = 0$，那么 $S$ 不能取数，$T$ 获胜
    否则的话，$S$ 取数之后，转为第一种情况 $\sum \equiv 0(\bmod 3)$，只不过最先取数的是 $T$
    将第一种情况结果取反，就是答案

int s[4];
string str;

void solve() {
    for (auto x : str) s[x % 3]++;
    int mo = 0;
    for (int i = 0; i <= 2; i++) mo += i * s[i];
    mo %= 3;

    if (mo == 0) {
        string res;
        s[0] % 2 ? res = "S" : res = "T";
        printf("%s\n", res.c_str());
    }
    else {
        if (s[mo] == 0) printf("T\n");
        else {
            string res;
            s[0] % 2 ? res = "T" : res = "S";
            printf("%s\n", res.c_str());
        }
    }
}

int main() {
    freopen("input.txt", "r", stdin);
    int T;
    cin >> T;
    int kase = 0;
    while (T--) {
        printf("Case %d: ", ++kase);
        memset(s, 0, sizeof s);
        cin >> str;
        solve();
    }
}

组合计数基础

重复元素的全排列方案数

定理 $n$ 个元素，分为 $m$ 组，其中本组元素全部相同，不同组元素不同，并且第 $i$ 组有 $p_i$ 个
总的排列数为

$$\frac{n!}{\prod_{k=1}^{m} p_k !}$$

Add Again

const int maxn = 15;
const ll one[13] = {
        0,
        1,
        11,
        111,
        1111,
        11111,
        111111,
        1111111,
        11111111,
        111111111,
        1111111111,
        11111111111,
        111111111111
};

int n;
ll fac[maxn];
int cnt[maxn];

void prework() {
    fac[0] = fac[1] = 1;
    for (int i = 2; i <= 12; i++) {
        fac[i] = fac[i-1] * (ll)i;
    }
}

int main() {
    freopen("input.txt", "r", stdin);
    prework();

    while (scanf("%d", &n) == 1 && n) {
        memset(cnt, 0, sizeof cnt);
        int sum = 0;
        for (int i = 0; i < n; i++) {
            int x;
            scanf("%d", &x);
            sum += x, cnt[x]++;
        }
        ll res = (ll)sum * fac[n-1];
        for (int i = 0; i <= 9; i++) res /= fac[cnt[i]];
        printf("%lld\n", res * one[n]);
    }
}

回文串计数举例

UVA12050

const int N = 20;
ll cnt[N];
int C;

void prework() {
    cnt[1] = 9, cnt[2] = 9;
    for (int i = 3; i < N; i++) {
        if (i & 1) cnt[i] = cnt[i-2] * 10;
        else cnt[i] = cnt[i-1];
    }
}

void solve() {
    // i len, C th
    int i = 1;
    for (; i < N; i++) {
        if (cnt[i] < C) C -= cnt[i];
        else break;
    }
    C--;
    string str(i, '0');
    int k = i/2;
    while (C) {
        str[k++] = '0' + C % 10;
        C /= 10;
    }
    str[i-1]++;
    for (int j = 0; j < i/2; j++) {
        str[j] = str[i-1-j];
    }
    printf("%s\n", str.c_str());
}

int main() {
    freopen("input.txt", "r", stdin);
    prework();
    // for (int i = 1; i < N; i++) debug(cnt[i]);
    while (scanf("%d", &C) == 1 && C) {
        solve();
    }
}