約数の個数の最大化 [yukicoder No.811]

https://yukicoder.me/problems/no/811

前提知識

• エラトステネスの篩の計算量

解説

https://yukicoder.me/submissions/338186

今回は答えを全探索する。
答えの候補MがNと共通の素因数をK個以上持つかは、2つの数を素因数分解して、同じ数の個数のうち少ない方の総和を取って、それがK以上かを見ればいい。
約数の個数も素因数分解後の各素因数の個数+1の総積になる。
なので、事前に1～Nの素因数分解を行っておこう。
これは、エラトステネスの篩っぽくやればできる。
計算量もこれを使えばO(NlogN)
わからない場合はエラトステネスの篩を勉強しよう。
　
あとは、K以上かを判別して、約数が最も多くて、小さいMを求めると答え。

int N, K;
int A[101010];
map<int, int> B[101010];
//---------------------------------------------------------------------------------------------------
void _main() {
	cin >> N >> K;

	rep(i, 1, N + 1) A[i] = i;
	rep(p, 2, N + 1) for (int i = p; i <= N; i += p) while (A[i] % p == 0) {
		B[i][p]++;
		A[i] /= p;
	}

	int ans = 0, ma = -1;
	rep(M, 1, N) {
		int k = 0;
		fore(p, B[N]) k += min(p.second, B[M][p.first]);
		if (k < K) continue;

		int yaku = 1;
		fore(p, B[M]) yaku *= p.second + 1;
		if (ma < yaku) {
			ans = M;
			ma = yaku;
		}
	}
	cout << ans << endl;
}