BOJ 24456 초콜릿 훔쳐 먹기

https://www.acmicpc.net/problem/24456

24456번: 초콜릿 훔쳐 먹기

 

1부터 $NM$까지의 모든 수에 대해 해당 수를 두 수의 곱으로 표현하는 모든 경우를 구하는 문제라고도 생각할 수 있습니다. 단순히 모든 약수를 확인한다면 $\mathcal{O}({(NM)}^2)$의 시간이 걸릴 것이라고 생각했고 커팅하는데 시간이 걸렸습니다.

 

커팅은 소인수분해를 하듯이 하면 됩니다. $x$의 약수를 확인할 때 $\sqrt{x}$까지의 수로 나누어지는지만 확인하면 두 수의 곱으로 표현하는 모든 경우의 수를 확인할 수 있습니다. $\sqrt{x} \times \sqrt{x}$은 항상 $x$보다 크기 때문입니다.

 

아래는 코드입니다.

 

#include <bits/stdc++.h>
#define FastIO ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define endl '\n'
#define ends ' '

using namespace std;

int T, n, m, k;

int32_t main(void) {
  FastIO;
  T = 1;
  //cin >> T;

  while (T--) {
    cin >> n >> m >> k;

    int cnt = n * m;
    int diff = abs(n - m);

    int ans = 0;

    while (cnt > 1) {
      cnt--;
      int flag = 0;
      for (int i = 1; i * i <= cnt; i++) {
        if (cnt % i) continue;
        int d = cnt / i;
        int dd = d - i;
        if (abs(dd - diff) <= k) {
          flag = 1;
          break;
        }
      }
      if (!flag) break;
      ans++;
    }

    cout << ans << endl;
  }

  return 0;
}