题目 | Factorial and Multiple

Denso Create Programming Contest 2022 Winter(AtCoder Beginner Contest 280)

D - Factorial and Multiple

https://atcoder.jp/contests/abc280/tasks/abc280_d

Time Limit: 2 sec / Memory Limit: 1024 MB

Score : $400$ points

Problem Statement

You are given an integer $K$ greater than or equal to $2$ .
Find the minimum positive integer $N$ such that $N!$ is a multiple of $K$ .

Here, $N!$ denotes the factorial of $N$ . Under the Constraints of this problem, we can prove that such an $N$ always exists.

Constraints

$2 \leq K \leq 10^{12}$
$K$ is an integer.

Input

The input is given from Standard Input in the following format:

K

Output

Print the minimum positive integer $N$ such that $N!$ is a multiple of $K$ .

Sample Input 1

30

Sample Output 1

5

$1! = 1$
$2! = 2 \times 1 = 2$
$3! = 3 \times 2 \times 1 = 6$
$4! = 4 \times 3 \times 2 \times 1 = 24$
$5! = 5 \times 4 \times 3 \times 2 \times 1 = 120$

Therefore, $5$ is the minimum positive integer $N$ such that $N!$ is a multiple of $30$ . Thus, $5$ should be printed.

Sample Input 2

123456789011

Sample Output 2

123456789011

Sample Input 3

280

Sample Output 3

7

题解

（这题比赛的时候用不正常的方法混过了，现在补一遍正解）

该题要分解质因数，这点应该比较好想，不过之后的处理方式才是重点。即：

对于分解好的数 $K = p_{0}^{a_{0}} p_{1}^{a_{1}} \dots p_{n}^{a_{n}} (p_{0}, p_{1}, \dots, p_{n} 为质数)$ ，如何求得最小的 $N!$ 满足 $K ∣ N!$

我们可以单独考虑每一个质数，对于 $p_{i}^{a_{i}}$ ，取 $N = p_{i} \cdot a_{i}$ 一定能满足条件，但是该答案不一定是最小的。具体举例来说：

如 $3^{4}$ ，取 $N = 3 \cdot 4 = 12$ ， $N! = 12 \dots \times 9 \times \dots \times 6 \times \dots \times 3 \times \dots$ ，可以看见， $9$ 里面实际上包含了两个 $3$ ，因此我们没有必要令 $N = 12$ ，只需要 $N = 9$ 即可。

那么如何求到最小的呢？分解质因数后能保证时间复杂度为 $\log$ 级别，因此我们从直接一个个算就行了。使用变量 $c n t$ 计数，计算 $i \cdot p_{i} (i = 1, 2, \dots)$ 内含有的 $p_{i}$ 因子个数 $n$ ，将 $c n t$ 加上 $n$ ，直到 $c n t \geq a_{i}$ 时， $i \cdot p_{i}$ 便是所求的 $N$ 。具体举例来说：

如 $3^{4}$ ，我们需要 $4$ 个 $3$ ，从 $1 \times 3$ 开始， $3$ 含有 $1$ 个 $3$ ， $6$ 含有 $1$ 个 $3$ ， $9$ 含有 $2$ 个 $3$ ，此时已经组成了 $4$ 个 $3$ ， $N = 9$

考虑完单个质数之后，整个 $K$ 的答案便是每个质数因子的答案的最大值。

代码

#include <bits/stdc++.h>
#define endl '\n'

using namespace std;

typedef long long ll;
const int MAXN = 1e6 + 10;
int prime[MAXN], primesize = 0;
bool not_prime[MAXN];
void init_prime()
{
    not_prime[0] = not_prime[1] = true;
    for (int i = 2; i < MAXN; i++)
    {
        if (!not_prime[i])
            prime[primesize++] = i;
        for (int j = 0; j < primesize && i * prime[j] < MAXN; j++)
        {
            not_prime[i * prime[j]] = true;
            if (i % prime[j] == 0)
                break;
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    init_prime();
    ll K;
    cin >> K;
    ll ans = 0;
    for (int i = 0; i < primesize; i++)
    {
        ll prm = prime[i], cnt = 0;
        if (prm * prm > K)
            break;
        while (!(K % prm))
        {
            K /= prm;
            cnt++;
        }
        ll n = 0;
        while (cnt > 0)
        {
            n += prm;
            int x = n;
            while (!(x % prm))
            {
                x /= prm;
                cnt--;
            }
        }
        ans = max(ans, n);
    }
    cout << max(ans, K) << endl;
    return 0;
}