Divisors of Power [yukicoder No.847]

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

前提知識

• 枝刈り全探索

解説

https://yukicoder.me/submissions/357485

まず、N^Kの正の約数であって、M以下のものというのはそんなに個数がなさそうな感じがする。
N^Kを素因数分解をして、適当な枝刈りをしながらDFSすれば通りそう。
　
まずは、Nを素因数分解して、その個数をすべてK倍しておこう。
あとは、各素因数について0個使う、1個使う、…といった要領でDFSしながら、約数を探索していこう。
ここで重要なのが、0個から使う個数を決めていくが、Mを超えた場合には、枝刈りをしよう。

ll N, K, M;
//---------------------------------------------------------------------------------------------------
vector<pair<ll, ll>> primes;
int dfs(int cu, ll tot) {
	if (cu == primes.size()) return 1;

	ll res = 0;
	rep(cnt, 0, primes[cu].second + 1) {
		ll tot2 = tot * fastpow(primes[cu].first, cnt);
		if (M < tot2) break;
		res += dfs(cu + 1, tot2);
	}
	return res;
}
//---------------------------------------------------------------------------------------------------
void _main() {
	cin >> N >> K >> M;

	auto ep = enumpr(N);
	fore(p, ep) primes.push_back({ p.first, p.second * K });

	cout << dfs(0, 1) << endl;
}