[백준 5768] Divide and Conquer (C#, C++) - soo:bak

문제 링크

5768번 - Divide and Conquer

설명

주어진 구간에서 약수의 개수가 가장 많은 수를 찾고 그 개수를 함께 출력하는 문제입니다. 약수 개수가 같으면 더 큰 수를 선택합니다. 두 수가 모두 0이면 종료합니다.

접근법

1부터 최댓값까지의 약수 개수를 미리 구해 둡니다. 각 수의 배수들에 1씩 더해주면 됩니다.

각 테스트에서 구간을 순회하며 약수 개수가 더 크거나, 같으면서 값이 더 큰 경우 갱신합니다.

---

Code

C#

using System;
using System.Text;

class Program {
  static void Main() {
    const int LIM = 5000;
    var divs = new int[LIM + 1];
    for (var i = 1; i <= LIM; i++) {
      for (var j = i; j <= LIM; j += i)
        divs[j]++;
    }

    var parts = Console.In.ReadToEnd().Split((char[])null, StringSplitOptions.RemoveEmptyEntries);
    var idx = 0;
    var sb = new StringBuilder();
    while (idx + 1 < parts.Length) {
      var m = int.Parse(parts[idx++]);
      var n = int.Parse(parts[idx++]);
      if (m == 0 && n == 0)
        break;

      var bestX = m;
      var bestY = divs[m];
      for (var x = m; x <= n; x++) {
        var y = divs[x];
        if (y > bestY || (y == bestY && x > bestX)) {
          bestY = y;
          bestX = x;
        }
      }
      sb.AppendLine($"{bestX} {bestY}");
    }

    Console.Write(sb);
  }
}

C++

#include <bits/stdc++.h>
using namespace std;

typedef vector<int> vi;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  const int LIM = 5000;
  vi divs(LIM + 1, 0);
  for (int i = 1; i <= LIM; i++) {
    for (int j = i; j <= LIM; j += i)
      divs[j]++;
  }

  int m, n;
  while (cin >> m >> n) {
    if (m == 0 && n == 0)
      break;
    int bestX = m, bestY = divs[m];
    for (int x = m; x <= n; x++) {
      int y = divs[x];
      if (y > bestY || (y == bestY && x > bestX)) {
        bestY = y;
        bestX = x;
      }
    }
    cout << bestX << " " << bestY << "\n";
  }

  return 0;
}