素因数分解ゲー! 今なら ABC D あたりに出てきそう
問題概要
正の整数 が与えられる。
が
の倍数となるような最小の正の整数
を求めよ。
制約
解法 (1):素因数分解
まず を素因数分解しよう。
とする。さらに、 をそれぞれ素因数分解していく。
の素因子を寄せ集めたときに、
が
個以上
が
個以上
- ...
が
個以上
という条件を満たす瞬間を捉えられればよい。
ただし注意点として、 が大きな素数であったとする。この場合は
と素因数分解していっても、
まで到達しない限り、
が素因数として登場しない。このままでは
の計算量 (整数
の素因数分解には
を要する) となって間に合わない。
そこで、次のようにする。
の素因数
(指数を
とする) ごとに考える。
に対して「
で何回割れるか」を求めて総和をとっていく。その値がはじめて
を超える瞬間の値を
とする。
素因数 ごとの
の最大値が答えである
指数 としてありうる値は高々
程度 (大きくても 30 くらい) である。よって、それぞれの素因数に対して
回程度の試行で済む。めちゃくちゃ速い。
コード
#include <bits/stdc++.h> using namespace std; // 素因数分解 vector<pair<long long, long long> > prime_factorize(long long n) { vector<pair<long long, long long> > res; for (long long p = 2; p * p <= n; ++p) { if (n % p != 0) continue; int num = 0; while (n % p == 0) { ++num; n /= p; } res.push_back(make_pair(p, num)); } if (n != 1) res.push_back(make_pair(n, 1)); return res; } // N が P で何回割れるか long long how_many(long long N, long long P) { long long res = 0; while (N % P == 0) { N /= P; ++res; } return res; } int main() { long long N; cin >> N; auto pf = prime_factorize(N); long long res = 0; for (auto pa : pf) { long long p = pa.first, e = pa.second; long long sum = 0; for (long long m = p; m <= N; m += p) { sum += how_many(m, p); if (sum >= e) { res = max(res, m); break; } } } cout << res << endl; }
解法 (2):かなり楽な方法
もう少し賢い方法でやってみよう! 結論から述べると、次の方法で解ける!!
を素因数分解したとき、素因数に
以上のもの (
とする) があるならば、
が答え
- そうでないならば、
を
で割ったあまりを求めていき、初めて 0 になったときの
が答え
まず、 の素因子
が
以上であるとしよう。このとき、
の指数
は
ということで確定する。よって、
というふうに表せる。ここで とく。このとき、
以外の素因数
に対しては、少なくとも
の時点で、
の
に対する指数が
以上となる。なぜなら
自身が
で
回割り切れるからだ。
一方、 より、
が成立するので、答えは
で確定する。
より大きい素因数がない場合
この場合は、 は高々
で抑えられる。なぜならどの素因数も
より小さく、その指数も
で抑えられるからだ。
よって、少なくとも 程度で
は
で割り切れることになる。この程度ならば愚直計算で間に合う。
コード
#include <bits/stdc++.h> using namespace std; // 素因数分解 (指数は要らない、素数のみ) vector<long long> prime_factorize(long long n) { vector<long long> res; for (long long p = 2; p * p <= n; ++p) { if (n % p != 0) continue; while (n % p == 0) { n /= p; } res.push_back(p); } if (n != 1) res.push_back(n); return res; } long long solve(long long N) { auto pf = prime_factorize(N); for (auto p: pf) if (p * p >= N) return p; long long amari = 1; for (long long M = 1; M <= N; ++M) { amari = (amari * M) % N; if (amari == 0) return M; } // no reach return -1; } int main() { long long N; cin >> N; cout << solve(N) << endl; }