AtCoder NoviStepsを埋めてみる(10) 素数判定・約数列挙・素因数分解の続きです。今回は整数系探索問題です。
Contents
- 1 B – Around Square
- 2 C – Digits in Multiplication
- 3 A – Sum and Product
- 4 092 – Beautiful Rectangle
- 5 C – Minimize Abs 2
- 6 C – Four Variables
- 7 C – Unexpressed
- 8 C – Remainder Minimization 2019
- 9 B – □□□□□
- 10 C – Max GCD 2
- 11 C – XYZ Triplets
- 12 C – 2026
- 13 D – Square Permutation
- 14 D – Happy New Year 2023
- 15 D – I hate Factorization
- 16 fermat – フェルマー方程式 (Fermat)
B – Around Square
問題の概要
N 以下の平方数のうち、最大のものを求めよ。
1 から N まで全探索して i^2 が N 以下である i の最大値を探せばよいです。
|
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()); long ans = 0; for (int i = 0; i <= N; i++) { long v = 1L * i * i; if (v <= N) ans = v; else break; } Console.WriteLine(ans); } } |
全探索ではなく計算で答えを出してもよいです。√N の整数部分を二乗すれば解が得られます。Math.Sqrt(N) は double 型を返しますが、double 型の精度は 10進数では約 15 桁なので N が大きな値の場合は注意が必要です（この問題は N ≦ 10^9 なので問題ない）。
|
1 2 3 4 5 6 7 8 9 10 |
class Program { static void Main() { int N = int.Parse(Console.ReadLine()); int m = (int)Math.Sqrt(N); Console.WriteLine(m * m); } } |
C – Digits in Multiplication
問題の概要
整数 N が与えられる。
F(A, B) を「正整数 A, B を 10 進表記したときの大きい方の桁数」と定義する。
例：F(3, 11) なら 2。
(A, B) が N = A × B を満たすように動くとき、F(A, B) の最小値を求めよ。
A × B = N となる A, B を全探索するのですが、A ≦ B という条件をつければ O(√N) で全探索できます。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
class Program { static void Main() { long N = long.Parse(Console.ReadLine()); int ans = int.MaxValue; for (int a = 1; a <= (int)Math.Sqrt(N); a++) { if (N % a == 0) { long b = N / a; int f = Math.Max(a.ToString().Length, b.ToString().Length); ans = Math.Min(ans, f); } } Console.WriteLine(ans); } } |
A – Sum and Product
問題の概要
整数 S, P が与えられる。
N + M = S, N × M = P を満たすような正の整数の組 (N, M) は存在するだろうか？
N, M を全探索します。N + M = S に対して N × M = P となる N, M は限られているので N × M = P（N ≦ M）であるペアを求め、これが N + M = S であるか確認して条件を満たしているなら “Yes” を出力します。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
class Program { static void Main() { string[] vs = Console.ReadLine().Split(); long S = long.Parse(vs[0]); long P = long.Parse(vs[1]); bool yes = false; for (int n = 1; n <= Math.Sqrt(P); n++) { if (P % n == 0) { long m = P / n; if (n + m == S) { yes = true; break; } } } Console.WriteLine(yes ? "Yes" : "No"); } } |
092 – Beautiful Rectangle
問題の概要
縦の長さと横の長さが整数である面積 N の長方形について、周の長さの最小値を求めよ。
a, b (a ≦ b) を全探索して a × b = N となるものを探します。a, b は長方形の縦横の長さなので周の長さであれば和を 2 倍すればよいです。そこから最小値を探します。
|
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()); long ans = long.MaxValue; for (int a = 1; a <= Math.Sqrt(N); a++) { if (N % a == 0) { long b = N / a; ans = Math.Min(ans, (a + b) * 2); } } Console.WriteLine(ans); } } |
C – Minimize Abs 2
問題の概要
正整数 D が与えられる。
非負整数 x, y に対する |x^2 + y^2 – D| の最小値を求めよ。
|x^2 + y^2 – D| を最小化するのであれば、できるだけ x^2 + y^2 を D に近づければよいです。x を 0 から √D まで全探索します。
仮の x の値を決め打ちして、D – x * x – y * y <= 0 である最小の y を二分探索法で取得します。このとき D - x * x - y * y の値は 0 以下の値になりますが、実はそれよりも少し大きい正の値のほうが適切だったという場合もあるので D - x * x - (y - 1) * (y - 1) の場合（ただし y - 1 ≧ 0）も調べます。これらの結果から絶対値を調べて最小になるものを解として出力します。 二分探索ではライブラリ ac-library-csharp の StlFunction.BinarySearch を使っています。 参考： ac-library-csharpを使ってみる
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
class Program { static void Main() { SourceExpander.Expander.Expand(); long D = long.Parse(Console.ReadLine()); long sqrtD = (long)Math.Sqrt(D); long ans = long.MaxValue; for (long x = 0; x <= sqrtD; x++) { long ok = sqrtD + 1; long ng = -1; long y = AtCoder.StlFunction.BinarySearch(ok, ng, mid => D - x * x - mid * mid <= 0); ans = Math.Min(ans, Math.Abs(D - x * x - y * y)); if (y - 1 >= 0) ans = Math.Min(ans, Math.Abs(D - x * x - (y - 1) * (y - 1))); } Console.WriteLine(ans); } } |
C – Four Variables
問題の概要
正整数 N が与えられる。
正整数の組 (A, B, C, D) であって、A × B + C × D = N を満たすものの個数を求めよ。
正整数の組 (A, B, C, D) を全探索するのは無理があります。しかし A × B ≦ N となる正整数の組 (A, B) であれば全探索可能です。C × D ≦ N となる正整数の組 (C, D) は内容的に前者とまったく同じです。
なので前者のそれぞれに対してこれに加算することで 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 33 |
class Program { static void Main() { int N = int.Parse(Console.ReadLine()); Dictionary<int, int> dic = new Dictionary<int, int>(); for (int a = 1; a <= N; a++) { int n = N / a; for (int b = 1; b <= n; b++) { if (a * b <= N) { if (!dic.ContainsKey(a * b)) dic.Add(a * b, 0); dic[a * b]++; } } } long ans = 0; var pairs = dic.ToArray(); foreach (var pair in pairs) { int m = N - pair.Key; if (dic.ContainsKey(m)) ans += 1L * dic[m] * pair.Value; } Console.WriteLine(ans); } } |
C – Unexpressed
問題の概要
整数 N が与えられる。
1 以上 N 以下の整数のうち、2 以上の整数 a, b を用いて a^b と表せないものはいくつあるだろうか？
N から 2 以上の整数 a, b を用いて a^b と表せるものの個数を引けばよいです。a の探索範囲は 2 以上 √N 以下です。b の探索範囲は 2 以上で a^b ≦ N を満たすものです。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
class Program { static void Main() { long N = long.Parse(Console.ReadLine()); HashSet<long> set = new HashSet<long>(); for (long a = 2; a <= Math.Sqrt(N); a++) { long v = a; for (int b = 2; b <= 60; b++) { v *= a; if (v <= N) set.Add(v); else break; } } long ans = N - set.Count; Console.WriteLine(ans); } } |
C – Remainder Minimization 2019
C – Remainder Minimization 2019
問題の概要
非負整数 L, R が与えられる。
2 つの整数 i, j を L ≦ i < j ≦ R を満たすように選ぶ。
(i × j) mod 2019 の最小値を求めよ。
(i × j) mod 2019 = (i mod 2019 × j mod 2019) mod 2019 です。なので L ≦ i < j ≦ R ではなく L ≦ i < j ≦ Math.Min(R, L + 2019) の範囲で i, j を全探索すればよいです。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
class Program { static void Main() { string[] vs = Console.ReadLine().Split(); int L = int.Parse(vs[0]); int R = int.Parse(vs[1]); R = Math.Min(R, L + 2019); int ans = int.MaxValue; for (int i = L; i <= R; i++) { for (int j = i + 1; j <= R; j++) { int v = (i % 2019) * (j % 2019); ans = Math.Min(ans, v % 2019); } } Console.WriteLine(ans); } } |
B – □□□□□
問題の概要
一辺の長さが 1 の正方形のタイルが n 枚ある。
これらのタイルのうちいくつかを重ならないように隙間なく並べて大きな長方形を作りたい。
出来上がる長方形はできるだけ正方形に近いほうがよいが、使わずに余るタイルの枚数もできるだけ少なくしたい。
（長方形の縦と横の長さの差の絶対値 + 余ったタイルの枚数）の最小値を求めよ。
a × b ≦ N (a ≦ b) となる a, b を全探索して（長方形の縦と横の長さの差の絶対値 + 余ったタイルの枚数）の最小値を求めます。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
class Program { static void Main() { int N = int.Parse(Console.ReadLine()); int ans = int.MaxValue; for (int a = 1; a <= N; a++) { int n = N / a; for (int b = 1; b <= n; b++) ans = Math.Min(ans, Math.Abs(a - b) + (N - a * b)); } Console.WriteLine(ans); } } |
C – Max GCD 2
問題の概要
整数 A, B が与えられる。
整数 x, y を A ≦ x < y ≦ B となるように選ぶときの gcd(x, y) の最大値を求めよ。
x, y を全探索するより、z は公約数になりうるかを考えたほうが速いです。z としてありえる値は B 未満です。
z の倍数が A 以上 B 以下の区間に複数存在するなら z は公約数になりえる数です。
|
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 |
class Program { static void Main() { string[] vs = Console.ReadLine().Split(); int A = int.Parse(vs[0]); int B = int.Parse(vs[1]); int ans = 0; for (int z = 1; z <= B; z++) { // z の倍数が区間 [A, B] に複数存在する int cnt = 0; for (int v = z; v <= B; v += z) { if (A <= v && v <= B) cnt++; if (cnt >= 2) break; } if (cnt >= 2) ans = z; } Console.WriteLine(ans); } } |
C – XYZ Triplets
問題の概要
f(n) を以下の 2 つの条件の両方を満たすような 3 つの整数の組 (x, y, z) の個数と定義する。
x, y, z は自然数
x^2 + y^2 + z^2 + xy + yz + zx = n
整数 N が与えられるので f(1), f(2), f(3), …, f(N) をそれぞれ求めよ。
x, y, z を全探索するのですが、二乗があるのと正整数同士の足し算なので探索範囲は √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 |
class Program { static void Main() { int N = int.Parse(Console.ReadLine()); int sqrtN = (int)Math.Sqrt(N); int[] counts = new int[N + 1]; for (int x = 1; x <= sqrtN; x++) { for (int y = 1; y <= sqrtN; y++) { for (int z = 1; z <= sqrtN; z++) { int v = x * x + y * y + z * z + x * y + y * z + z * x; if (v <= N) counts[v]++; } } } for (int i = 1; i <= N; i++) Console.WriteLine(counts[i]); } } |
C – 2026
問題の概要
正整数 n が次の条件を満たす時、n を 良い整数 と呼ぶことにする。
0 < x < y かつ x^2 + y^2 = n を満たす整数の組 (x, y) がただ 1 つ存在する。
正整数 N が与えられる。
N 以下の良い整数をすべて列挙せよ。
二乗があることと正整数同士の足し算なので x, y の探索範囲は √N までです。それぞれの(x, y) で x^2 + y^2 を計算し、ひとつの整数組でしか得られなかった整数が良い整数なので、それを出力します。
|
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 { static void Main() { int N = int.Parse(Console.ReadLine()); int sqrtN = (int)Math.Sqrt(N); int[] counts = new int[N + 1]; for (int x = 1; x <= sqrtN; x++) { for (int y = x + 1; y <= sqrtN; y++) { int v = x * x + y * y; if (v <= N) counts[v]++; else break; } } List<int> ans = new List<int>(); for (int i = 1; i <= N; i++) { if (counts[i] == 1) ans.Add(i); } Console.WriteLine(ans.Count); Console.WriteLine(string.Join(" ", ans)); } } |
D – Square Permutation
問題の概要
数字のみからなる、長さ N の文字列 S が与えられる。
S を並べ替えてできる文字列を十進法の整数として解釈したもののうち、平方数であるようなものがいくつあるか求めよ。
平方数を先につくって、S を並べ替えてこれらと一致させられるかを考えます。一致させられるかどうかは両者をソートして各要素がすべて一致するかを調べればいいのですが、先頭に 0 を付加することで一致するケースもあるので S のほうが長い場合は ‘0’ を追加して長さを同じにしてから一致判定をしています。
|
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 |
class Program { static void Main() { int N = int.Parse(Console.ReadLine()); char[] S = Console.ReadLine().ToArray(); List<long> vs = new List<long>(); { long v = 0; while (true) { if ((v * v).ToString().Length > N) break; vs.Add(v * v); v++; } } Array.Sort(S); int ans = 0; foreach (long v in vs) { // S を並べ替えて v を作れるか？ List<char> list = v.ToString().ToList(); // S のほうが短い場合は絶対に不可能 if (list.Count > S.Length) continue; // list のほうが短い場合は先頭に '0' を追加することでできるかもしれない int len_diff = S.Length - list.Count; for (int i = 0; i < len_diff; i++) list.Add('0'); // 両者をソートして各要素を比較する list = list.OrderBy(_ => _).ToList(); bool ok = true; for (int i = 0; i < S.Length; i++) { if (S[i] != list[i]) { ok = false; break; } } if (ok) ans++; } Console.WriteLine(ans); } } |
D – Happy New Year 2023
問題の概要
正整数 N が与えられる。
N は 2 つの相異なる素数 p, q を用いて N = p^2 × q と表せることがわかっている。
p, q を求めよ。
N の最大値が 9 × 10^18 であることと、探す素数のペアが N = p^2 × q を満たすものであることから 10^7 以下の素数をすべて求めます。そのための処理にエラトステネスの篩を使っています。そのためのメソッドである GetPrimes メソッドはここで定義 しています。
最初に N を割り切ることができる p^2 を探します。見つかったら N / (p * p) が q です。見つからなかった場合は p は 10^7 を超える大きな素数です。この場合は q は小さい素数になるので N を割り切ることができる q を探します。見つかった場合は N / q の平方根が 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 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 |
class Program { // bool[] Eratosthenes(int max) // List<int> GetPrimes(int max) 上記定義のとおり static void Main() { int T = int.Parse(Console.ReadLine()); List<long> primes = GetPrimes((int)Math.Pow(10, 7)); for (long i = 0; i < T; i++) { long N = long.Parse(Console.ReadLine()); Solve(N); } void Solve(long N) { long p = 0; long q = 0; foreach (long prime in primes) { if (N % (prime * prime) == 0) { p = prime; q = N / (prime * prime); break; } } if (p == 0) { foreach (long prime in primes) { if (N % prime == 0) { q = prime; p = (long)Math.Round(Math.Sqrt(N / prime)); break; } } } Console.WriteLine($"{p} {q}"); } } } |
D – I hate Factorization
問題の概要
A^5 – B^5 = X を満たす整数の組 (A, B) をひとつ示せ。
ただし解は必ず存在することが保証されている。
A と B の探索範囲がどうなるのかがこの問題の肝です。(A + 1)^5 – A^5 > X となるのであれば、それよりも大きな値のなかから A, B を探そうとしても絶対に見つかりません。実験してみると Math.Pow(10, 9) < Math.Pow(120, 5) – Math.Pow(119, 5) であることがわかり、(A, B) の探索範囲も絶対値が 120 まででよいことがわかります。
|
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() { int X = int.Parse(Console.ReadLine()); long Pow5(long v) => v * v * v * v * v; for (long a = -120; a <= 120; a++) { for (long b = -120; b <= 120; b++) { if (Pow5(a) - Pow5(b) == X) { Console.WriteLine($"{a} {b}"); return; } } } } } |
fermat – フェルマー方程式 (Fermat)
素数 P と自然数 N が与えられる。
x^N + y^N ≡ z^N (mod P) をみたす整数 x, y, z (0 ≦ x, y, z ≦ P – 1) の組 (x, y, z) の個数を求めよ。
最初に x^N % P を計算しておきます。x の範囲は 0 以上 P 未満です。mod P を考えるのでそれより大きな数で考えるのは無駄です。あとは 0 ≦ a, b ≦ P – 1 を全探索します。
x^N % P == a で y^N % P == b のとき z^N == (a + b) % 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 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 |
class Program { // 繰り返し二乗法で a の b 乗 を m で割ったあまりを求める static long ModPow(long a, long b, long m) { long ans = 1; while (0 < b) { if ((b & 1) == 1) ans = (ans * a) % m; a = (a * a) % m; b >>= 1; } return ans; } static void Main() { int P = int.Parse(Console.ReadLine()); int N = int.Parse(Console.ReadLine()); int[] counts = new int[P]; for (int i = 0; i < P; i++) { long v = ModPow(i, N, P); counts[v]++; } long ans = 0; for (int x = 0; x < P; x++) { if (counts[x] == 0) continue; for (int y = 0; y < P; y++) { if(counts[y] == 0) continue; int z = (x + y) % P; ans += 1L * counts[x] * counts[y] * counts[z]; } } for (int a = 0; a < P; a++) { if (counts[a] == 0) continue; for (int b = 0; b < P; b++) { if(counts[b] == 0) continue; int c = (a + b) % P; ans += 1L * counts[a] * counts[b] * counts[c]; } } Console.WriteLine(ans); } } |
