AtCoder NoviStepsを埋めてみる(8) エラトステネスの篩の続きです。今回もエラトステネスの篩です。難しめの問題に挑戦します。
030 – K Factors（★5）
問題の概要
2 以上 N 以下の整数のうち、K 種類以上の素因数を持つものの個数を求めよ。
長さ N + 1 の配列を定義し、素因数 x をもつのであれば（素因数 x の倍数であれば）インクリメントすることで素因数の種類数を記録していくことができます。そのなかから値が K 以上のものを数えればよいです。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 |
class Program { // エラトステネスの篩で max 以下の整数が素数かどうかを調べる static bool[] Eratosthenes(int max) { bool[] is_primes = new bool[max + 1]; Array.Fill(is_primes, true); is_primes[0] = false; is_primes[1] = false; int ceiling = (int)(Math.Sqrt(max)) + 1; for (int cur = 2; cur <= ceiling; cur++) { if (!is_primes[cur]) continue; for (long v = 1L * cur * cur; v <= max; v += cur) is_primes[v] = false; } return is_primes; } // エラトステネスの篩の結果から max 以下のすべての素数のリストを返す static List<int> GetPrimes(int max) { List<int> res = new List<int>(); var is_primes = Eratosthenes(max); for (int i = 0; i <= max; i++) { if (is_primes[i]) res.Add(i); } return res; } static void Main() { int max = 10000000; List<int> primes = GetPrimes(max + 10); int[] A = new int[max + 1]; foreach (long prime in primes) { for (long i = prime; i <= max; i += prime) A[i]++; } string[] vs = Console.ReadLine().Split(); int N = int.Parse(vs[0]); int K = int.Parse(vs[1]); int ans = 0; for (int i = 1; i <= N; i++) { if (A[i] >= K) ans++; } Console.WriteLine(ans); } } |
E – Ringo’s Favorite Numbers 3
E – Ringo’s Favorite Numbers 3
問題の概要
素因数がちょうど 2 種類であり、その各素因数でその数が割り切れる回数は偶数回であるものを 400 number と定義する。
Q 個のクエリが与えられるので、与えられた A 以下の最大の 400 number の値を求めよ。
ただし A 以下の 400 number は常に存在することが保証されている。
「各素因数でその数が割り切れる回数は偶数回」とはその数が平方数であることと同値です。また素因数が 2 種類しかないことはその数の平方根もまた 2 種類の素因数しか持たないことを意味しています。
2 種類の素因数しか持たないものを列挙するのであれば 030 – K Factors（★5） の方法がそのまま使えます。
A 以下で最大のものを探すのであれば二分探索法が有効です。二分探索の処理はライブラリ ac-library-csharp の StlFunction.BinarySearch メソッドを用いています。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 |
using AtCoder; class Program { // bool[] Eratosthenes(int max) // List<int> GetPrimes(int max) 上記定義のとおり static void Main() { int max = 1000000; List<int> primes = GetPrimes(max + 10); int[] counts = new int[max + 1]; foreach (int p in primes) { for (int i = p; i <= max; i += p) counts[i]++; } List<long> V = new List<long>(); for (long i = 1; i <= max; i++) { if(counts[i] == 2) V.Add(i * i); } int Q = int.Parse(Console.ReadLine()); for (int i = 0; i < Q; i++) { long x = long.Parse(Console.ReadLine()); int ok = -1; int ng = V.Count; int idx = StlFunction.BinarySearch(ok, ng, mid => V[mid] <= x); Console.WriteLine(V[idx]); } } } |
E – Many LCMs
問題の概要
長さ N の正整数列 A が与えられる。
k = 0, 1, 2, …, N – 1 について、A のなかから A[k] を除いた N – 1 個の要素の最小公倍数を 998244353 で割ったあまりを求めよ。
T 個のテストケースが与えられるので、それぞれについて答えを求めよ。
そのつど出力すべき最小公倍数を計算していては TLE 必至なので A 全体の最小公倍数 (LCM) を事前に計算しておきます。そのあと A[k] が取り除かれることで LCM がどう変化するのか考えます。
LCM で用いられている素因数の使用回数と A[k] で用いられている素因数の使用回数を比較します。もし両者が同じだと A[k] が取り除かれることで最小公倍数の値が小さくなります。その素因数の使用回数が A のなかで最大のものと二番目のものとの差だけその使用回数が少なくなるのです。
使用回数が少なくなる素因数とその回数がわかればあとは LCM をその素因数でその回数だけ割ればいいのですが、わり算の剰余に対して除算はできないので逆元を計算して掛け合わせることで対応します。
D – Coprime 2 で定義した PrimeFactorization クラス を使っています。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 |
class Program { // 逆元を返す static long Inverse(long a, long mod) { if (a < 0) a += mod; long b = mod, u = 1, v = 0; while (b > 0) { long t = a / b; a -= t * b; swap(ref a, ref b); u -= t * v; swap(ref u, ref v); } u %= mod; if (u < 0) u += mod; return u; void swap(ref long a, ref long b) { long c = a; a = b; b = c; } } static void Main() { int T = int.Parse(Console.ReadLine()); long mod = 998244353; PrimeFactorization pf = new PrimeFactorization(10000000); for (int i = 0; i < T; i++) { int N = int.Parse(Console.ReadLine()); int[] A = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); Solve(N, A); } void Solve(int N, int[] A) { Dictionary<long, List<int>> lcm_dic = new Dictionary<long, List<int>>(); List<Dictionary<long, int>> F = new List<Dictionary<long, int>>(); foreach (var v in A) F.Add(pf.Solve(v)); foreach (var f in F) { foreach (var pair in f) { if (!lcm_dic.ContainsKey(pair.Key)) { List<int> list = new List<int>(); list.Add(pair.Value); lcm_dic.Add(pair.Key, list); } else { lcm_dic[pair.Key].Add(pair.Value); } } } // 各素因数が使われている回数を降順ソートする // 同時にこの結果から最小公倍数を求める long lcm = 1; foreach (var pair in lcm_dic) { lcm_dic[pair.Key] = pair.Value.OrderByDescending(_ => _).ToList(); lcm *= (long)Math.Pow(pair.Key, lcm_dic[pair.Key][0]); lcm %= mod; } // A[i] がもつ素因数の使用回数と最小公倍数がもつ素因数の使用回数を比較する // 同じ回数の素因数がある場合、A[i] を取り除くことで最小公倍数の値が変わってしまう // 減ってしまう素因数の種類と個数から出力する解を算出する List<long> ans = new List<long>(); foreach (var f in F) { // 使用回数が減少する素因数とその使用回数 Dictionary<long, int> diff = new Dictionary<long, int>(); foreach (var pair in f) { if (lcm_dic[pair.Key][0] == pair.Value) { if (lcm_dic[pair.Key].Count >= 2) diff.Add(pair.Key, pair.Value - lcm_dic[pair.Key][1]); else diff.Add(pair.Key, pair.Value); } } long ans0 = lcm; foreach (var pair in diff) { // 最小公倍数を（使用回数が減少する素因数の減少回数乗）で割ればよいが // 剰余の割り算ができないので逆元を掛けることで対応する long inv = Inverse((long)Math.Pow(pair.Key, pair.Value), mod); ans0 *= inv; ans0 %= mod; } ans.Add(ans0); } Console.WriteLine(string.Join(" ", ans)); } } } |
E – LCM Sequence
問題の概要
正整数 n について A[n] を 1, 2, …, n の最小公倍数として定義する。
正整数 L, R が与えられます。数列 (A[L], A[L+1], …, A[R]) の中には何種類の整数が含まれるか求めよ。
数列 A は広義単調増加数列です。A[n] に含まれる素因数を考えます。
A[2] -> {2}
A[3] -> {2, 3}
A[4] -> {2, 2, 3}
A[5] -> {2, 2, 3, 5}
A[6] -> {2, 2, 3, 5}
A[7] -> {2, 2, 3, 5, 7}
A[8] -> {2, 2, 2, 3, 5, 7}
n が素数であるとき素因数の種類が増えるので A[n] の値は増えます。また素数でなくても単一素数の正の整数乗になっている場合（素数冪という）はその素数が素因数の使用回数を 1 増やします。なので L + 1 以上、R 以下の素数冪の個数を数えれば n が L から R まで増えたときの個数の増加数がわかります。これに 1（最初の A[L] のぶん）を加えたものが解となります。
R が大きな値になっていますが、R – L がそれほど大きな値でなければ 097 – Primes in an Interval でも用いたエラストテネスの区間篩でなんとかなります。
素数冪であるかどうかは 10^7 までの素数をすべて求めてその整数乗を計算します。素数冪であっても R よりも大きなものはいらないのでそんなに処理に時間はかかりません。
PrimeInterval クラス は ここで定義 しています。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 |
using System.Numerics; // PrimeInterval クラスは 上記定義のとおり class Program { // bool[] Eratosthenes(int max) // List<int> GetPrimes(int max) は 上記定義のとおり static void Main() { int max = 10000000; List<int> primes = GetPrimes(max + 10); string[] vs = Console.ReadLine().Split(); long L = long.Parse(vs[0]); long R = long.Parse(vs[1]); PrimeInterval primeInterval = new PrimeInterval(L, R); // 10000000 以下の素数の整数乗を求める //（それより大きな素数は 2乗 した段階で確実に R を超えてしまうのでやる必要はない） HashSet<long> set = new HashSet<long>(); foreach (long prime in primes) { set.Add(prime); Int128 v = prime; for (int i = 0; i < 30; i++) { v *= prime; if (v > R) break; set.Add((long)v); } } int ans = 1; for (long i = L + 1; i <= R; i++) { if (set.Contains(i) || primeInterval.IsPrime(i)) ans++; } Console.WriteLine(ans); } } |
