競技プログラミング必携アルゴリズムスニペット集
素因数分解
void factorize(int n, vector<int>& primes) {
for (int d = 2; 1LL * d * d <= n; ++d) {
if (n % d == 0) {
primes.push_back(d);
while (n % d == 0) n /= d;
}
}
if (n > 1) primes.push_back(n);
}
ユークリッドの互除法による GCD / LCM
int gcd(int x, int y) { return y ? g ...
9月27日 15:18 投稿