divs

ソースコード

 1#include <iostream>
 2#include <set>
 3#include <vector>
 4#include <map>
 5using namespace std;
 6
 7// Osa_k
 8namespace titan23 {
 9
10  struct Osa_k {
11    int n;
12    vector<int> min_factor;
13
14    Osa_k(const int n) : n(n), min_factor(n+1) {
15      iota(min_factor.begin(), min_factor.end(), 0);
16      for (int i = 2; i*i <= n; ++i) {
17        if (min_factor[i] == i) {
18          for (int j = 2; j <= n/i; ++j) {
19            if (min_factor[i*j] > i) {
20              min_factor[i*j] = i;
21            }
22          }
23        }
24      }
25    }
26
27    vector<int> p_factorization(int n) const {
28      vector<int> ret;
29      while (n > 1) {
30        ret.emplace_back(min_factor[n]);
31        n /= min_factor[n];
32      }
33      return ret;
34    }
35
36    map<int, int> p_factorization_map(int n) const {
37      map<int, int> ret;
38      while (n > 1) {
39        ++ret[min_factor[n]];
40        n /= min_factor[n];
41      }
42      return ret;
43    }
44  };
45}  // namespace titan23

仕様

Warning

doxygenfile: Cannot find file “titan_cpplib/math/divs.cpp