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 |
class Program { // bool[] Eratosthenes(int max) // List<int> GetPrimes(int max) 上記定義のとおり 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 をその素因数でその回数だけ割ればいいのですが、わり算の剰余に対して除算はできないので逆元を計算して掛け合わせることで対応します。
|
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 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 |
class Program { // bool[] Eratosthenes(int max) // List<int> GetPrimes(int max) 上記定義のとおり // 事前に取得した素数を利用して複数の値の素因数分解をする static Dictionary<int, int>[] PrimeFactorizations(HashSet<int> prime_set, int[] A) { Dictionary<int, int> PrimeFactorization(int v) { Dictionary<int, int> dic = new Dictionary<int, int>(); if (prime_set.Contains(v)) { dic.Add(v, 1); return dic; } foreach (int p in prime_set) { while (v % p == 0) { v /= p; if (!dic.ContainsKey(p)) dic.Add(p, 0); dic[p]++; } if (prime_set.Contains(v)) { dic.Add(v, 1); break; } if (v == 1) break; } return dic; } Dictionary<int, int>[] res = new Dictionary<int, int>[A.Length]; for (int i = 0; i < A.Length; i++) res[i] = PrimeFactorization(A[i]); return res; } // 逆元を返す 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 max = 10000000; List<int> primes = GetPrimes(max + 10); HashSet<int> prime_set = new HashSet<int>(primes); int T = int.Parse(Console.ReadLine()); long mod = 998244353; 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<int, List<int>> lcm_dic = new Dictionary<int, List<int>>(); Dictionary<int, int>[] F = PrimeFactorizations(prime_set, A); 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<int, int> diff = new Dictionary<int, 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 よりも大きなものはいらないのでそんなに処理に時間はかかりません。
|
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 |
using System.Numerics; class Program { // bool[] Eratosthenes(int max) // List<int> GetPrimes(int max) 上記定義のとおり // エラトステネスの区間篩 (R が 10^14 以下で R - L が 10^7 以下なら何とか対応できる) class IntervalPrimes { long L = 0; bool[] IsPrimes = []; public IntervalPrimes(long left, long R) { L = left; IsPrimes = new bool[R - L + 1]; Array.Fill(IsPrimes, true); int max = (int)Math.Sqrt(R) + 10; List<int> primes = GetPrimes(max); foreach (long p in primes) { long start = L % p == 0 ? L / p * p : L / p * p + p; for (long i = start; i <= R; i += p) { if (i != p) IsPrimes[i - L] = false; // 素数の倍数であれば合成数（ただし1倍は除く） } } // 上の処理だけでは 1 がふるい落とせていないので注意 if (L == 0) IsPrimes[1] = false; if (L == 1) IsPrimes[0] = false; int ans = 0; for (int i = 0; i < R - L + 1; i++) { if (IsPrimes[i]) ans++; } } public bool IsPrime(long v) { return IsPrimes[v - L]; } } static (long, long) ReadLong2() { string[] vs = Console.ReadLine().Split(); return (long.Parse(vs[0]), long.Parse(vs[1])); } static void Main() { int max = 10000000; List<int> primes = GetPrimes(max + 10); (long L, long R) = ReadLong2(); IntervalPrimes p = new IntervalPrimes(L, 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) || p.IsPrime(i)) ans++; } Console.WriteLine(ans); } } |
