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

D - Factorial and Multiple

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$.

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.

123456789011

123456789011

280

7

### 题解

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

### 代码

#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;
}