[yukicoder] No. 847 Divisors of Power
問題
方針
素因数分解
\( N \) を素数 \( p_i \) と 正の整数 \( a_i \) を用いて、 \( N = p_1^{a_1}p_2^{a_2} \cdots p_n^{a_n} \) と表すと、
\[ N^K = p_1^{a_1K}p_2^{a_2K} \cdots p_n^{a_nK} \]
と表現できます。\( N^K \) の約数を、\( f(b_1, b_2, \cdots, b_n) \ (0 \leq b_i \leq a_iK)\) とすると、
\[ f(b_1, b_2, \cdots, b_n) = p_1^{b_1}p_2^{b_2}\cdots p_n^{b_n}\]
となります。
深さ優先探索
\( f(b_1, b_2, \cdots, b_n) \) の \( b_i \) 組み合わせを全探索します。どのように全探索をするかというと、深さ優先探索で、枝刈りをしながら行います。下の図がイメージになります。
掛け算を行いながら深さ優先探索を行うので、その値が \( M \) を超えたとき、その探索を止めます。
コード
#include <bits/stdc++.h> using namespace std; typedef long long ll; vector<set<ll>> v; ll N, K, M; int cnt = 0; void dfs(int n, ll x) { if (v.size() == n) { cnt++; return; } for (ll i : v[n]) { if (x * i <= M) { dfs(n + 1, x * i); } else { return; } } } int main() { cin >> N >> K >> M; map<ll, ll> m; ll t = N; for (int i = 2; i * i <= N; i++) { while (t % i == 0) { t /= i; m[i]++; } if (t == 1) break; } if (t != 1) { m[t]++; } for (auto i = m.begin(); i != m.end(); i++) { ll p = i->first; ll k = K * i->second; ll cnt = 1; ll P = p; set<ll> s{1}; while (P <= M && cnt <= k) { s.insert(P); P *= p; cnt++; } if (s.size() != 1) { v.push_back(s); } } dfs(0, 1); cout << cnt << "\n"; return 0; }
ディスカッション
コメント一覧
まだ、コメントがありません