This documentation is automatically generated by online-judge-tools/verification-helper
#include "nt/coprime_factorization.hpp"
/*
互いに素な整数 p1, p2, ..., pk を用いて n_i = prod p_i^e_i と表す.
[21,60,140,400]
[3,7,20], [[(0,1),(1,1)],[(0,1),(2,1)],[(1,1),(2,1)],[(2,2)]]
*/
template <typename T>
pair<vc<T>, vvc<pair<int, int>>> coprime_factorization(vc<T> nums) {
vc<T> basis;
for (T val: nums) {
vc<T> new_basis;
for (T x: basis) {
if (val == 1) {
new_basis.eb(x);
continue;
}
vc<T> dat = {val, x};
FOR(p, 1, len(dat)) {
FOR(i, p) {
while (1) {
if (dat[p] > 1 && dat[i] % dat[p] == 0) dat[i] /= dat[p];
elif (dat[i] > 1 && dat[p] % dat[i] == 0) dat[p] /= dat[i];
else break;
}
T g = gcd(dat[i], dat[p]);
if (g == 1 || g == dat[i] || g == dat[p]) continue;
dat[i] /= g, dat[p] /= g, dat.eb(g);
}
}
val = dat[0];
FOR(i, 1, len(dat)) if (dat[i] != 1) new_basis.eb(dat[i]);
}
if (val > 1) new_basis.eb(val);
swap(basis, new_basis);
}
sort(all(basis));
vvc<pair<int, int>> res(len(nums));
FOR(i, len(nums)) {
T x = nums[i];
FOR(j, len(basis)) {
int e = 0;
while (x % basis[j] == 0) x /= basis[j], ++e;
if (e) res[i].eb(j, e);
}
}
return {basis, res};
}
#line 1 "nt/coprime_factorization.hpp"
/*
互いに素な整数 p1, p2, ..., pk を用いて n_i = prod p_i^e_i と表す.
[21,60,140,400]
[3,7,20], [[(0,1),(1,1)],[(0,1),(2,1)],[(1,1),(2,1)],[(2,2)]]
*/
template <typename T>
pair<vc<T>, vvc<pair<int, int>>> coprime_factorization(vc<T> nums) {
vc<T> basis;
for (T val: nums) {
vc<T> new_basis;
for (T x: basis) {
if (val == 1) {
new_basis.eb(x);
continue;
}
vc<T> dat = {val, x};
FOR(p, 1, len(dat)) {
FOR(i, p) {
while (1) {
if (dat[p] > 1 && dat[i] % dat[p] == 0) dat[i] /= dat[p];
elif (dat[i] > 1 && dat[p] % dat[i] == 0) dat[p] /= dat[i];
else break;
}
T g = gcd(dat[i], dat[p]);
if (g == 1 || g == dat[i] || g == dat[p]) continue;
dat[i] /= g, dat[p] /= g, dat.eb(g);
}
}
val = dat[0];
FOR(i, 1, len(dat)) if (dat[i] != 1) new_basis.eb(dat[i]);
}
if (val > 1) new_basis.eb(val);
swap(basis, new_basis);
}
sort(all(basis));
vvc<pair<int, int>> res(len(nums));
FOR(i, len(nums)) {
T x = nums[i];
FOR(j, len(basis)) {
int e = 0;
while (x % basis[j] == 0) x /= basis[j], ++e;
if (e) res[i].eb(j, e);
}
}
return {basis, res};
}