\(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';
}