yukicoder バレンタインコンテスト2021 B Giri 解説
問題
1~nからn-1個を選んで作れる最小公倍数のうち、その最小値を求め、998244353で割った余りを求めよ。
前提
- エラトステネスの篩
解説
まず除外すべき1つの数は自明に、1~nの中の最大の素数である。
次にn-1個の数の最小公倍数を求め方について、結果が非常に大きな値になる可能性があるためlcm
関数を使って求めることはできない。
この手の、n個全ての数の最小公倍数を求めたいが、結果が非常に大きくなる可能性があるからmodを取る問題の求め方は決まっていて、各要素を素因数分解すればよい。
各要素を素因数分解し、各素因数の種類とその最大個数が得られれば、(素因数)^(その個数)の全ての積が最小公倍数になる。
後は、上記をmodを取りながら計算すればよい。
高速素因数分解を行うためにエラトステネスの篩を行うため、計算量はO(n loglog n)
となる。
実装
#include <bits/stdc++.h> using namespace std; const long long MOD = 998244353; /// エラトステネスの篩 struct Eratosthenes { vector<bool> is_prime; /// nまでの素数一覧 vector<int> primes; /// 整数xの最小の素因数 vector<int> min_prime_factor; Eratosthenes(const int n) { min_prime_factor.resize(n + 1); /// nまでの素数一覧 is_prime.assign(n + 1, true); is_prime[0] = is_prime[1] = false; min_prime_factor[0] = min_prime_factor[1] = 1; for (int i = 2; i <= n; i++) { if (is_prime[i]) { for (int j = 2 * i; j <= n; j += i) { is_prime[j] = false; if (min_prime_factor[j] == 0) min_prime_factor[j] = i; } primes.push_back(i); min_prime_factor[i] = i; } } } /** * xの素因数の種類を取得 * @param x n以下の数値を指定する必要がある */ set<int> get_prime_factors(int x) { set<int> s; while (x > 1) { s.insert(min_prime_factor[x]); x /= min_prime_factor[x]; } return s; } /** * xの素因数とその数を取得 * @param x n以下の数値を指定する必要がある */ map<int, int> get_prime_factor_and_cnt(int x) { map<int, int> mp; while (x > 1) { mp[min_prime_factor[x]]++; x /= min_prime_factor[x]; } return mp; } }; signed main() { cin.tie(0); ios::sync_with_stdio(false); int n; cin >> n; auto e = Eratosthenes(n); auto ma = e.primes.back(); map<int, int> mp; for (int i = 1; i <= n; i++) { if (ma == i) continue; auto tmp = e.get_prime_factor_and_cnt(i); for (auto e : tmp) { mp[e.first] = max(mp[e.first], e.second); } } long long ans = 1; for (auto e : mp) { for (int i = 0; i < e.second; i++) { (ans *= e.first) %= MOD; } } cout << ans << endl; }