D - Factorial and Multiple Editorial by cn449
別解\(K\) が \(10^6\) 以上の素因数を持つとき
その素因数を \(p\) とおくと、 明らかに答えは \(p\) 以上で、\(K \leq 10^{12}\) より \(K/p < p\) なので、\(K/p \in \{ 1,2, \ldots, p-1 \}\) であるから答えは \(p\) となる。
\(K\) が \(10^6\) 以上の素因数を持たないとき
\(K \leq 10^{12}\) より \(K\) は \(10^4\) 以下の素因数を高々 \(200\) 個、\(10^4\) より大きく \(10^6\) 以下の素因数を高々 \(2\) 個しか持たないので \((2 \times 10^6)!\) が \(K\) の倍数となる。よって答えは高々 \(2 \times 10^6\) なので、以下の実装例のように昇順に調べていけばよい。
実装
実装上では \(10^6\) 以上の素因数の有無を直接判定しなくとも、答えが \(2 \times 10^6\) より大きければその時点でまだ登場していない \(K\) の素因数を出力すると正答を得ることができる。
#include <iostream>
#include <numeric>
using namespace std;
typedef long long ll;
int main() {
ll k;
cin >> k;
for (ll i = 1; i <= 2000000; i++) {
k /= gcd(k, i);
if (k == 1) {
cout << i << '\n';
return 0;
}
}
cout << k << '\n';
}
posted:
last update: