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