AtCoder NoviStepsを埋めてみる(9) エラトステネスの篩 1D編の続きです。今回は素数判定・約数列挙・素因数分解です。
別のところで定義した PrimeFactorization クラスを使っています。PrimeFactorization クラスの定義は ここを参照 してください。
Contents
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); } } |
