This documentation is automatically generated by competitive-verifier/competitive-verifier
素因数分解をする.
primefact(x)
:
x
を素因数分解した結果を vector<pair>
で返す.
各要素について,first
に素因数,second
に冪指数を格納する.
x
が $1$ 以下の場合,空の配列を返す.#pragma once
#ifndef call_include
#define call_include
#include <bits/stdc++.h>
using namespace std;
#endif
vector<pair<long long, int>> primefact(long long x) {
vector<pair<long long, int>> res;
for(long long i = 2; i * i <= x; i++) {
if(x % i) continue;
int ex = 0;
while(x % i == 0) {
x /= i;
ex++;
}
res.emplace_back(i, ex);
}
if(x > 1) res.emplace_back(x, 1);
return res;
}
#line 2 "math/primefact.cpp"
#ifndef call_include
#define call_include
#include <bits/stdc++.h>
using namespace std;
#endif
vector<pair<long long, int>> primefact(long long x) {
vector<pair<long long, int>> res;
for(long long i = 2; i * i <= x; i++) {
if(x % i) continue;
int ex = 0;
while(x % i == 0) {
x /= i;
ex++;
}
res.emplace_back(i, ex);
}
if(x > 1) res.emplace_back(x, 1);
return res;
}