AtCoder NoviStepsを埋めてみる(9) エラトステネスの篩 1D編の続きです。今回は素数判定・約数列挙・素因数分解です。
別のところで定義した PrimeFactorization クラスを使っています。PrimeFactorization クラスの定義は ここを参照 してください。
012 – Primality Test
問題の概要
N が素数であるかどうかを判定せよ。
前回 PrimeFactorization クラスを定義したのでこれを使います。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
// PrimeFactorization クラス は上記定義のとおり class Program { static void Main() { long N = long.Parse(Console.ReadLine()); int sqrt = (int)Math.Sqrt(N); PrimeFactorization pf = new PrimeFactorization(sqrt + 5); Console.WriteLine(pf.IsPrime(N) ? "Yes" : "No"); } } |
ライブラリを使わない方法
|
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 |
class Program { static void Main() { long N = long.Parse(Console.ReadLine()); Console.WriteLine(IsPrime(N) ? "Yes" : "No"); bool IsPrime(long v) { if (v <= 1) return false; if (v == 2 || v == 3) return true; if (v % 2 == 0 || v % 3 == 0) return false; // 偶数はすべて消したので奇数しか残っていない。 // 偶数で割れるかチェックするのは無意味なので奇数で割れるかだけチェックする // この確認は N までやる必要はない。√N まででよい（誤差が心配なので +5 している）。 long max = (long)Math.Sqrt(v) + 5; for (int i = 3; i <= max; i += 2) { if (i >= v) return true; // 自分自身の他に N を割り切れる整数は見つからなかった if (v % i == 0) return false; } return true; } } } |
C – Factors of Factorial
問題の概要
整数 N が与えられる。N! の正の約数の個数を 10^9 + 7 で割った余りを求めよ。
約数の個数は素因数分解したときの各素因数の指数に 1 を足したものの総積です。
|
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 |
// PrimeFactorization クラス は上記定義のとおり class Program { static void Main() { int N = int.Parse(Console.ReadLine()); long mod = (long)Math.Pow(10, 9) + 7; int sqrt = (int)Math.Sqrt(N); PrimeFactorization pf = new PrimeFactorization(sqrt + 5); Dictionary<long, int> dic = new Dictionary<long, int>(); for (int i = 1; i <= N; i++) { var res = pf.Solve(i); foreach (var pair in res) { if (!dic.ContainsKey(pair.Key)) dic.Add(pair.Key, 0); dic[pair.Key] += pair.Value; } } long ans = 1; foreach (var pair in dic) { ans *= pair.Value + 1; ans %= mod; } Console.WriteLine(ans); } } |
075 – Magic For Balls（★3）
問題の概要
整数 x が書かれたボールを叩くと以下の操作が行われる。
x が素数でない場合：叩かれたボールを消滅させ、整数 a が書かれたボールと整数 b が書かれたボールを追加する。a, b は ab = x かつ a ≧ 2, b ≧ 2 を満たす整数から自由に選ぶことができる。
x が素数である場合：なにも起こらない。
魔法を 1 回使うと、現在あるすべてのボールを同時に叩くことができる（魔法を使う以外の手段でボールを叩くことはできない）。
整数 N が書かれたボールが 1 個だけある。
すべてのボールに書かれている数を素数にするのであれば最小で何回の操作を行う必要があるだろうか？
ボールを叩く行為はボールに書かれた数を 1 を用いない 2 つの整数の積に変換することと同じです。素因数の個数（同じ素因数でも別物として数える）を求めて、それを何回半分にすれば 1 になるかを考えればよいです。
|
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 |
// PrimeFactorization クラス は上記定義のとおり class Program { static void Main() { long N = long.Parse(Console.ReadLine()); PrimeFactorization pf = new PrimeFactorization(1000000); var dic = pf.Solve(N); int cnt = dic.Sum(_ => _.Value); int ans = 0; while (cnt > 1) { if(cnt % 2 == 0) cnt = cnt / 2; else cnt = cnt / 2 + 1; ans++; } Console.WriteLine(ans); } } |
D – Staircase Sequences
問題の概要
整数からなる公差 1 の等差数列のうち、総和が N であるものはいくつあるだろうか？
数列 A { a, a + 1, …, b – 1, b } の総和を考えます。
まず、この数列の長さは b – a + 1 となります。次に、数列 A と 数列 A の順序を反転させた 数列 B{ b, b – 1, …, a + 1, a } との和を計算してみます。すると数列 C は { a + b, a + b, …, a + b, a + b } とすべての要素が同じになります。なので 数列 A の総和は (a + b)(b – a + 1) / 2 です。これが N になるものを探せばよいので、二元一次方程式 (a + b)(b – a + 1) = 2N の整数解の個数が求める解です。
a, b が整数なので (a + b) と (b – a + 1) も整数です。
X = a + b, Y = b – a + 1 と置くと X と Y は 2N の約数を昇順にならべたときに前から取っていったものと後ろから取っていったもののペアになります。
X = a + b, Y = b – a + 1 を a, b について解くと、a = (X – Y + 1) / 2, b =（X + Y -１）/ 2 となります。a, b は整数でなければならないのですが、そのためには X と Y の偶奇は異なっていなければなりません。
2N の約数をすべて求め（2N を割り切ることができる i をみつけたら N / i とペアにしてしまえばよい）、偶奇が異なるペアの数を数えます。ここでは i < N / i であるものだけを数え、答えを倍にしています。i を増やしながら順番に割り切れるか調べ、i が √2N を超えたら終了しています（誤差に注意）。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
class Program { static void Main() { long N = long.Parse(Console.ReadLine()); N *= 2; int ans = 0; for (long i = 1; i <= N; i++) { if (N % i == 0 && i % 2 != (N / i) % 2 && i < N / i) ans += 2; if (i * i >= N) break; } Console.WriteLine(ans); } } |
D – Div Game
問題の概要
正の整数 N が与えられる。N に対して、以下の操作を繰り返し行うことを考える。
① 以下の条件を全て満たす正の整数 z を選ぶ。
ある素数 p と正の整数 e を用いて z = p^e と表せる。
N が z で割り切れる。
以前の操作で選んだどの整数とも異なる。
② N を、N / z に置き換える。
上記操作を最大で何回行うことができるか求めよ。
N を素数の整数乗で割っていくのですが、割る回数を多くしたいのであればできるだけ少ない数で割りたいです。また以前の操作で選んだ数は選べないので、素数 p で割り切ることができるのであれば、p, p~2, p^3 のような順で割っていきたくなります。
素因数分解すれば素数 p を容易に発見することができます。あとは低い次数から割っていけばよいです。
|
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 |
// PrimeFactorization クラス は上記定義のとおり class Program { static void Main() { long N = long.Parse(Console.ReadLine()); int sqrt = (int)Math.Sqrt(N); PrimeFactorization pf = new PrimeFactorization(sqrt + 5); var dic = pf.Solve(N); int ans = 0; foreach (var pair in dic) { int v = pair.Value; for (int i = 1; i <= pair.Value; i++) { v -= i; if (v >= 0) ans++; else break; } } Console.WriteLine(ans); } } |
D – Disjoint Set of Common Divisors
D – Disjoint Set of Common Divisors
問題の概要
正整数 A, B が与えられる。
A と B の正の公約数の中からいくつかを選ぶ。
ただし、選んだ整数の中のどの異なる 2 つの整数についても互いに素でなければならない。
最大でいくつ選べるだろうか？
A と B の最大公約数について考えます。その 2 つの素因数を選ぶのであればどう選んでも互いに素です。また 1 はつねに公約数となり、他の整数とは互いに素です。
なので最大公約数を素因数分解して素因数の種類数をもとめ、これに 1 を加えたものが解となります。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
// PrimeFactorization クラス は上記定義のとおり class Program { static void Main() { long GCD(long a, long b) => b > a ? GCD(b, a) : (b == 0 ? a : GCD(b, a % b)); string[] vs = Console.ReadLine().Split(); long A = long.Parse(vs[0]); long B = long.Parse(vs[1]); long gcd = GCD(A, B); int sqrt = (int)Math.Sqrt(gcd); PrimeFactorization pf = new PrimeFactorization(sqrt + 5); var dic = pf.Solve(gcd); int ans = dic.Count + 1; Console.WriteLine(ans); } } |
D – Partition
問題の概要
整数 N, M が与えられる。
長さ N で各要素の総和が M となる正整数列 A を考える。
A の最大公約数が取りうる最大値を求めよ。
求める最大公約数を ans と置くと A の各要素は ans の倍数でなければなりません。M は ans の倍数の総和なので M もまた ans の倍数です。これは ans は M の約数であることを意味しています。
A の各要素を具体的に決めようとすると一例として { ans, ans, ans, ….., M – (N – 1) × ans } が挙げられます。M – (N – 1) × ans が ans を下回ってはダメです。方程式 ans ≦ M – (N – 1) × ans を解くと ans ≦ M / N となります。M の約数 で M / N 以下である最大のものが解となります。
約数を全列挙するためのメソッドを定義します。1 から N まで全部調べる必要はありません。約数には昇順に並べたとき前側と後ろ側を掛け算すると N になる性質を利用して時間計算量 O(√N) で求めています。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
// 約数全列挙 static long[] GetDivisors(long N) { List<long> divisors = new List<long>(); int sqrt = (int)Math.Min(Math.Sqrt(N) + 5, N); for (int v = 1; v <= sqrt; v++) { if (N % v == 0) { divisors.Add(v); divisors.Add(N / v); } } return divisors.Distinct().OrderBy(_ => _).ToArray(); } |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
class Program { static void Main() { string[] vs = Console.ReadLine().Split(); int N = int.Parse(vs[0]); int M = int.Parse(vs[1]); long[] divisors = GetDivisors(M); int max = M / N; long ans = 1; foreach (var div in divisors) { if (div <= max) ans = div; } Console.WriteLine(ans); } } |
C – N Coloring
問題の概要
整数 N が与えられる。
以下の条件を満たす長さ N の正整数列 A をひとつ出力せよ。
i が j の約数（i < j）ならば、A[i] ≠ A[j]。
数列に現れる値の最大値が最小になる。
長さ N + 1 の配列を定義し、全体を 1 で初期化します。そして i が j の約数なら（つまり j が i の倍数であるなら）（ただし i < j） A[j] = A[i] + 1 に更新します。この処理を i が 1 から N まで繰り返します。これで数列に現れる値の最大値を最小にすることができます。
最後に A[0] 以外の要素を出力します。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
class Program { static void Main() { int N = int.Parse(Console.ReadLine()); int[] A = new int[N + 1]; Array.Fill(A, 1); for (int i = 1; i <= N; i++) { for (int j = i + i; j <= N; j += i) A[j] = A[i] + 1; } Console.WriteLine(string.Join(" ", A.Skip(1))); } } |
C – 約数かつ倍数
問題の概要
2 個の正整数 A, B が与えられる。
A! の約数であり、かつ B! の倍数でもあるような正整数の個数を 1,000,000,007 で割った余りを求めよ。
数えなければならないものは B! の倍数 なので B! がもつ素因数を持たないものは数える必要はありません。A! を B! で割ってしまい、商の約数の個数を数えればよいです。
実際には A! / B! を計算してから約数を求めるのではなく、 (B + 1), (B + 2), …, A を素因数分解して各素因数の指数に 1 を加えたものの総積を計算しています。
|
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 |
// PrimeFactorization クラス は上記定義のとおり class Program { static void Main() { string[] vs = Console.ReadLine().Split(); long A = long.Parse(vs[0]); long B = long.Parse(vs[1]); int max = (int)Math.Pow(10, 5); PrimeFactorization pf = new PrimeFactorization(max); Dictionary<long, int> prime_factors = new Dictionary<long, int>(); for (long i = B + 1; i <= A; i++) { var dic = pf.Solve(i); foreach (var pair in dic) { if(!prime_factors.ContainsKey(pair.Key)) prime_factors.Add(pair.Key, 0); prime_factors[pair.Key] += pair.Value; } } long ans = 1; long mod = (long)Math.Pow(10, 9) + 7; foreach (var pair in prime_factors) { ans *= pair.Value + 1; ans %= mod; } Console.WriteLine(ans); } } |
D – DivRem Number
問題の概要
正整数 N が与えられる。
以下の条件を満たす 正整数 m の総和を求めよ。
「N を m で割った商とあまりが等しい」
N を m で割った商とあまりを k と置くと、N = k × m + k となり、変形すると N = k (m + 1) となります。これは (m + 1) は N の約数であり、m は N の約数から 1 を引いたものとなります（ただしこれは必要条件であって十分条件ではないので注意）。
N の約数から m の候補を探して m > 0 && N / m == N % m であるものの総和を計算します。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
class Program { // GetDivisors メソッドは上記定義のとおり static void Main() { long N = long.Parse(Console.ReadLine()); long[] divisors = GetDivisors(N); long ans = 0; foreach (var div in divisors) { long m = div - 1; if (m > 0 && N / m == N % m) // 十分性のチェック ans += m; } Console.WriteLine(ans); } } |
C – Product and GCD
問題の概要
各要素の値はわからないが、各要素の総積が P であることがわかっている長さ N の正整数列 A があります。A の最大公約数として最大のものを求めよ。
各要素の総積がわかっているのでこれを素因数分解します。最大公約数を最大化するためにはできるだけ均等にすべての要素に素因数を割り振っていけばよいです。P の素因数 p が k 個あるのであれば k / N 個ずつ割り振っていくことになります。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
// PrimeFactorization クラス は上記定義のとおり class Program { static void Main() { string[] vs = Console.ReadLine().Split(); long N = long.Parse(vs[0]); long P = long.Parse(vs[1]); PrimeFactorization pf = new PrimeFactorization((int)Math.Sqrt(P) + 5); var factors = pf.Solve(P); long ans = 1; foreach (var factor in factors) { long cnt = factor.Value / N; for (int i = 0; i < cnt; i++) ans *= factor.Key; } Console.WriteLine(ans); } } |
D – Factorial and Multiple
問題の概要
2 以上の整数 K が与えられる。
正の整数 N であって、N! が K の倍数となるようなもののうち最小のものを求めよ。
K を素因数分解してみます。仮に K が 2 × 3 × 5 ならこの 3 つの素因数を含む N! は 1 × 2 × 3 × 4 × 5 です。問題は 2^3 × 3^4 × 5 のようなケースです。素因数 2 を含む N は 2 の倍数ですが、
2: 2（1 個）
4: 2^2（2 個）
6: 2 × 3（1 個）
8: 2^3（3 個）
10: 2 × 5（2 個）
とちょっとややこしいです。
なので K を素因数分解したあとそれぞれの素因数の個数をみたす最小の N を求め、そのなかで最大の N を求めることで解を求めています。
|
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 |
// PrimeFactorization クラス は上記定義のとおり class Program { static void Main() { long K = long.Parse(Console.ReadLine()); PrimeFactorization pf = new PrimeFactorization((int)Math.Pow(10, 6) + 10); var factors = pf.Solve(K); long ans = 0; foreach (var factor in factors) { long p = factor.Key; int cnt = factor.Value; for (long i = 1; cnt > 0; i++) { long v = factor.Key * i; ans = Math.Max(ans, v); while (v % p == 0 && cnt > 0) { v /= p; cnt--; } } } Console.WriteLine(ans); } } |
E – Flatten
問題の概要
長さ N 個の正整数列 A が与えられる。
次の条件を満たすような正整数列 B を考える。
条件：
1 ≦ i < j ≦ N を満たすどのような i, j についても A[i] × B[i] = A[j] × B[j] が成り立つ。
このような正整数列 B の各要素の総和の最小値を 10^9 + 7 で割った余りを求めよ。
A[i] × B[i] が A の最小公倍数になるように B[i] を定めればよいです。A の各要素を素因数分解をしてここから最小公倍数 (LCM) を求めます。そして LCM にあって A の各要素にない素因数を調べれば B[i] がわかります。あとはこの総和を求めればよいです。
|
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 |
// PrimeFactorization クラス は上記定義のとおり class Program { static void Main() { int N = int.Parse(Console.ReadLine()); int[] A = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); PrimeFactorization pf = new PrimeFactorization((int)Math.Pow(10, 6) + 10); Dictionary<long, int>[] F = new Dictionary<long, int>[N]; Dictionary<long, int> lcm = new Dictionary<long, int>(); for (int i = 0; i < N; i++) { var factors = pf.Solve(A[i]); F[i] = factors; foreach (var f in factors) { if(!lcm.ContainsKey(f.Key)) lcm.Add(f.Key, 0); lcm[f.Key] = Math.Max(lcm[f.Key], f.Value); } } // x^y % mod を求める long Pow(long x, int y, int mod) { long v = 1; for (int i = 0; i < y; i++) { v *= x; v %= mod; } return v; } long ans = 0; int mod = (int)Math.Pow(10, 9) + 7; for (int i = 0; i < N; i++) { // lcm にあって F[i] にはないものは？ long b = 1; foreach (var f in lcm) { if (!F[i].ContainsKey(f.Key)) b *= ModPow(f.Key, f.Value, mod); else if(F[i][f.Key] < f.Value) b *= ModPow(f.Key, f.Value - F[i][f.Key], mod); b %= mod; } ans += b; ans %= mod; } Console.WriteLine(ans); } } |
D – 756
問題の概要
整数 N が与えられる。
N! の約数のうち、ちょうど 75 個持つ正の整数 は何個あるでしょうか？
約数を 75 個もつ整数を素因数分解したときにどのように表されるかを考えます。素因数の個数と約数の個数の関係から以下のパターンしか考えられません。
A^74
A^2 × B^24
A^4 × B^14
A^4 × B^4 × C^2
また N! がもつ素因数の最大値は N 以下の最大の素数です。なので N 以下の素数で条件を満たす素数 A, B, C があるか全探索します。
|
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 |
// PrimeFactorization クラス は上記定義のとおり class Program { static void Main() { int N = int.Parse(Console.ReadLine()); List<int> primes = GetPrimes(N); PrimeFactorization pf = new PrimeFactorization(100); Dictionary<long, int> F = new Dictionary<long, int>(); for (int i = 2; i <= N; i++) { Dictionary<long, int> factors = pf.Solve(i); foreach (var f in factors) { if(!F.ContainsKey(f.Key)) F.Add(f.Key, 0); F[f.Key] += f.Value; } } int ans = 0; // A ^ 74 で表される約数があれば数える foreach (var p in primes) { if (F.ContainsKey(p) && F[p] >= 74) ans++; } // A ^ 2 * B ^ 24 または A ^ 4 * B ^ 14 で表される約数があれば数える（A, B は異なる） foreach (var p1 in primes) { foreach (var p2 in primes) { if (p1 == p2) continue; if (F.ContainsKey(p1) && F[p1] >= 2 && F.ContainsKey(p2) && F[p2] >= 24) ans++; if (F.ContainsKey(p1) && F[p1] >= 4 && F.ContainsKey(p2) && F[p2] >= 14) ans++; } } // A ^ 4 * B ^ 4 * C ^ 2 で表される約数があれば数える（A, B, C は互いに異なる） foreach (var p1 in primes) { foreach (var p2 in primes) { foreach (var p3 in primes) { if (p1 == p3 || p2 == p3) continue; // A と B の個数が同じなのでダブルカウントしないように A < B という条件をつける if (p1 < p2 && F.ContainsKey(p1) && F[p1] >= 4 && F.ContainsKey(p2) && F[p2] >= 4 && F.ContainsKey(p3) && F[p3] >= 2) ans++; } } } Console.WriteLine(ans); } } |
