Prime

题意

给定一个数 \(a\)，按照算术基本定理分解后给出指数序列，输出最小的 \(n\)，满足 \(n! \bmod a = 0\)。

思路

首先，指数序列的长度很小，不妨直接打表（不打表的话无脑线性筛筛一下即可）。

其次，既然需要被 \(p\) 整除，那么阶乘中就需要有对应数量的因子。

举个例子，如果 \(p\) 的质因子 \(7\) 的指数为 \(4\)，那么阶乘中就最好有 \(1 \times 7, 2 \times 7, 3 \times 7, 4 \times 7\)，也就是说，我们期望 \(n\) 至少为 \(28\)。

想到这里，数据量比较特殊的时候，底数和指数乘积的最大值就是答案。

那么，如果指数大于等于底数呢？就像上述例子，出现 \(7 \times 7\) 的时候，我们需要的 \(7\) 的个数就小于等于指数的大小了，因此我们不能直接取底数和指数的乘积。

这边有两个思路：

数位 \(dp\) 线性预处理；
设底数为 \(x\)，指数为 \(p\)，对于所需的最大 \(x \times p\)，二分 \(p\)。

本题数据量特别友好，我们直接二分就行。

我们在 \([1, p]\) 内进行二分。对于 \(mid\)，我们计算 \(i \in [1, mid], i \times p\) 中 \(p\) 因子的总数：

总数是什么呢？观察一下可以发现，它就是以 \(mid\) 为首项，\(\frac{1}{x}\) 为公比的等比数列的前 \(n\) 项和。

因而我们可以解得答案。

值得一提的是，上述计算方式和进制有关联，这为数位 \(dp\) 提供了思路。

时间复杂度：\(O(n \log m)\)

对应AC代码

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define pii pair<int, int>
#define pci pair<char, int>
#define fs first
#define sc second
#define pb emplace_back
#define all(x) x.begin(),x.end()

const int N = 2e5 + 10, inf = 0x3f3f3f3f3f3f3f3f;

vector<int> pri = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541};

void solve(){
    int m;
    cin >> m;
    int ans = 1;
    auto check = [&](int x, int p, int mid) -> bool {
        int ans = 0;
        for (int i = 1; i <= mid; i *= x) ans += (mid / i);
        return ans >= p;
    };
    for(int t=0;t<m;t++) {
        int x = pri[t], p;
        cin >> p;
        int l = 1, r = p, mid;
        while(l < r){
            mid = (l + r) >> 1;
            if(check(x, p, mid)) r = mid;
            else l = mid + 1;
        }
        ans = max(ans, x * r);
    }
    cout << ans << '\n';
}

signed main(){
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int t = 1;
    cin >> t;
    while(t --) solve();
}

更强的数据可以看这里：#530. 「LibreOJ β Round #5」最小倍数 - 题目 - LibreOJ (loj.ac)