「CF2153E」Zero Trailing Factorial

发表于 分类于 本文字数： 852 阅读时长 ≈ 3 分钟

Description

Link：CF2153E

设 vp(x!)v_p(x!) 表示 x!x! 可以分解出多少个 pp 的乘积。

勒让德定理：

  • 当 pp 为质数时

vp(x!)=∑j=1⌊log⁡kx⌋⌊xpj⌋v_p(x!) = \sum_{j = 1}^{\lfloor \log_k x \rfloor} \left\lfloor \frac{x}{p^j} \right\rfloor

  • 当 pp 为合数时，记 p=∑i=1mpicip = \sum_{i = 1}^m p_i^{c_i}

vp(x!)=min⁡i=1m⌊vpi(x!)ci⌋v_p(x!) = \min_{i = 1}^m \left\lfloor \frac{v_{p_i}(x!)}{c_i} \right\rfloor

设

wk(a,b)={min⁡(vk(a!),vk(b!))if vk(a!)≠vk(b!);10100otherwise.w_k(a, b) = \begin{cases} \min(v_k(a!), v_k(b!)) & \text{if }v_k(a!) \neq v_k(b!) \text{;}\\ 10^{100} & \text{otherwise.} \end{cases}

设

fm(a,b)=min⁡2≤k≤mwk(a,b)f_m(a, b) = \min_{2 \leq k \leq m} w_k(a, b)

给出两个整数 n,mn, m，你需要计算 ∑1≤x<nfm(x,n)\sum\limits_{1 \leq x < n}f_m(x, n)。

数据范围：2≤n≤m≤1072 \leq n \leq m \leq 10^7。可以证明给定条件下答案严格小于 1010010^{100}。

时空限制：33s / 512512MiB。

Solution

设 p0p_0 是小于等于 nn 中最大的质数，对于 x<p0x < p_0 显然有 fm(x,n)=0f_m(x, n) = 0（因为取 k=p0k = p_0 即有 wk(x,n)=0w_k(x, n) = 0）。

打表发现 10710^7 以内，相邻素数的差值最大为 154154。于是我们真正要考虑的 p0≤x<np_0 \leq x < n 部分，实际上并不大。

性质：对于 a≤ba \leq b，有 vk(a!)≤vk(b!)v_k(a!) \leq v_k(b!)。

由于 a!∣b!a! \mid b!，易证。

性质：wk(a,b)≥min⁡i=1mwpici(a,b)w_k(a, b) \geq \min_{i = 1}^m w_{p_i^{c_i}}(a, b)。

对于 1≤i≤m1 \leq i \leq m，设 ai=⌊vpi(a!)ci⌋a_i = \left\lfloor \frac{v_{p_i}(a!)}{c_i} \right\rfloor，bi=⌊vpi(b!)ci⌋b_i = \left\lfloor \frac{v_{p_i}(b!)}{c_i} \right\rfloor。

  • 若 vk(a!)=vk(b!)v_k(a!) = v_k(b!)，则 wk(a,b)=10100w_k(a, b) = 10^{100}，不等式成立。
  • 若 vk(a!)≠vk(b!)v_k(a!) \neq v_k(b!)，即 min⁡{ai}<min⁡{bi}\min\{a_i\} < \min\{b_i\}，设 ax=min⁡{ai}a_x = \min\{ a_i \}，则 ax<bxa_x < b_x，此时有 wk(a,b)=ax=wpxcx(a,b)w_k(a, b) = a_x = w_{p_x^{c_x}}(a, b)。

该性质告诉我们，我们只需枚举形如 k=pck = p^c 的数计算 fm(x,n)f_m(x, n) 即可。

性质：只需枚举形如 k=pck = p^c 且 pp 被 [p0,n][p_0, n] 中至少一个数整除的数。

记 n!=p0!(p0+1)⋯nn! = p_0!(p_0 + 1) \cdots n，若 pp 不被 [p0,n][p_0, n] 中的某个数整除，则必有 vk(p0!)=vk(n!)v_k(p_0!) = v_k(n!)。

性质：答案必定严格小于 1010010^{100}。

考虑将 x−1x - 1 变成 xx，对于 xx 的某个质因数 pp，必有 vp((x−1)!)<vp(x!)v_p((x - 1)!) < v_{p}(x!)，因为 ⌊xp⌋\left\lfloor \frac{x}{p} \right\rfloor 发生了变化。

于是将 [p0,n][p_0, n] 中所有数的质因数拿出来，枚举形如 k=pck = p^c 的数计算 fm(x,n)f_m(x, n) 即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
#include <bits/stdc++.h>

#define debug(a) std::cout << #a << "=" << (a) << ' '

using s64 = long long;
using u64 = unsigned long long;

/* 取 min */
template <class T>
inline void chmin(T &x, const T &y) {
    if (x > y) {
        x = y;
    }
}
/* 取 max */
template <class T>
inline void chmax(T &x, const T &y) {
    if (x < y) {
        x = y;
    }
}

/* ----- ----- ----- 正文 ----- ----- ----- */

const int V = 1e7, MaxV = V + 10;

int primeCount, prime[MaxV], fac[MaxV];
int low[MaxV];

void sieve(const int &n) {
    for (int i = 2; i <= n; i ++) {
        if (!fac[i]) {
            prime[++ primeCount] = i, fac[i] = i;
            low[i] = i;
        }
        for (int j = 1; j <= primeCount; j ++) {
            if (prime[j] > fac[i] || prime[j] > n / i) break;
            fac[i * prime[j]] = prime[j];
            low[i * prime[j]] = prime[j] * (i % prime[j] == 0 ? low[i] : 1);
        }
    }
}

int n, m;

int factorialIndex(int n, int p) {
    int cnt = 0;
    for (int v = p;; v *= p) {
        cnt += n / v;

        if (v > n / p) {
            break;
        }
    }
    return cnt;
}

void work() {
    std::cin >> n >> m;

    int p0 = n;
    while (fac[p0] != p0) {
        p0 --;
    }

    std::vector<int> key;

    for (int i = p0; i <= n; i ++) {
        int x = i;
        while (x > 1) {
            key.push_back(fac[x]);
            x /= low[x];
        }
    }

    std::sort(key.begin(), key.end());
    key.erase(std::unique(key.begin(), key.end()), key.end());

    s64 ans = 0;
    for (int i = p0; i < n; i ++) {
        int cur = 0x3f3f3f3f;
        for (int p : key) {
            int cnti = factorialIndex(i, p),
                cntn = factorialIndex(n, p);
            for (int v = p, c = 1;; v *= p, c ++) {
                int vi = cnti / c,
                    vn = cntn / c;
                if (vi < vn) {
                    chmin(cur, vi);
                }

                if (v > m / p) {
                    break;
                }
            }
        }
        ans += cur;
    }

    std::cout << ans << '\n';
}

int main() {
    std::ios::sync_with_stdio(0);
    std::cin.tie(0);

    sieve(V);

    int T;
    std::cin >> T;
    
    while (T --) {
        work();
    }

    return 0;
}

/**
 *  心中无女人
 *  比赛自然神
 *  模板第一页
 *  忘掉心上人
**/