AtCoder NoviStepsを埋めてみる(11) 整数系探索問題の続きです。今回も整数系探索問題ですが、難しめの問題に挑戦することにします。
085 – Multiplication 085（★4）
問題の概要
正の整数 K が与えられる。
abc = K を満たす正の整数 (a, b, c) (a ≦ b ≦ c) の組がいくつあるかを求めよ。
全探索しようとすると厳しそうですが、すべての正の整数ではなく K の約数であれば全探索できそうです。それでも三重ループにすると TLE してしまうケースがひとつだけあります。a と b が決まれば c は計算すればわかるので（K が a * b で割り切れて商が b 以上であればよい）二重ループで実装できます。
約数を全列挙する GetDivisors メソッドはここで定義 されています。
|
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 |
class Program { static void Main() { long K = long.Parse(Console.ReadLine()); long[] divisors = GetDivisors(K); int len = divisors.Length; int ans = 0; for (int x = 0; x < len; x++) { // divisors[x]^3 > K だと明らかに大きすぎる if (Math.Pow(divisors[x], 3) > K) break; for (int y = x; y < len; y++) { // divisors[x] * divisors[y]^2 > K だと明らかに大きすぎる if (Math.Pow(divisors[y], 2) > K / divisors[x]) break; // K が divisors[x] * divisors[y] で割り切れて // 商が divisors[y] 以上のとき c として適切である if ((K / divisors[x]) % divisors[y] == 0) { long c = K / divisors[x] / divisors[y]; if (c >= divisors[y]) ans++; } } } Console.WriteLine(ans); } } |
C – ABC conjecture
問題の概要
正の整数 N が与えられる。
A ≦ B ≦ C かつ ABC ≦ N であるような正の整数の組 (A, B, C) の個数を求めよ。
似たような問題が前にありましたが 今回は ABC = N ではなく ABC ≦ N なので全探索を頑張るしかありません。N の値が 10^11 なのでなんとかできます。
|
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() { long N = long.Parse(Console.ReadLine()); long ans = 0; for (long a = 1; a <= N; a++) { if (a * a * a > N) // a としては明らかに大きい break; for (long b = a; b <= N; b++) { if (a * b * b > N) // b としては明らかに大きい break; long v = N / (a * b); ans += v - (b - 1); // v の倍数で b 以上の個数 } } Console.WriteLine(ans); } } |
D – 2-variable Function
問題の概要
整数 N が与えられる。以下の条件をすべて満たす最小の整数 X を求めよ。
X は N 以上である。
非負整数 (a, b) の組であって、X = a^3 + a^2 × b + a × b^2 + b^3 を満たすようなものが存在する。
a を全探索するのですが、三乗があるので N の三乗根まででよいです。a を決め打ちしたら X を N 以上にする最小の b の値は二分探索法で求めます。a に対応する b の値が定まったら実際に X の値を計算し、そのなかから最小のものを出力します。
二分探索ではライブラリ 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 |
class Program { static void Main() { long N = long.Parse(Console.ReadLine()); long X(long a, long b) => a * a * a + a * a * b + a * b * b + b * b * b; long ans = long.MaxValue; for (long a = 0; a <= N; a++) { if (a * a * a > N) break; long ok = (int)Math.Pow(10, 6) + 1; long ng = -1; long b = AtCoder.StlFunction.BinarySearch(ok, ng, mid => X(a, mid) >= N); ans = Math.Min(ans, X(a, b)); } Console.WriteLine(ans); } } |
