[Leetcode][970] Powerful Integers

문제 : https://leetcode.com/problems/powerful-integers/

---

1이상의 양수인 x, y, 0이상의 bound가 입력으로 주어진다.

i, j 가 0이상의 양수라 할때, x^i + y^i <= bound 인 x^i + y^i 의 집합을 구하라.

---

변수 a, b를 만들고 1로 초기화한다. answer set을 하나 만든다.

a, b에 각각 x, y를 곱해가면서 a + b가 bound 이하이면 answer에 넣는다.

a + b가 bound 초과면 반복문을 빠져나온다.

for(int a=1; a<bound; a *= x) {
  for(int b=1; b<bound; b *= y) {
    if(a + b <= bound) answer.insert(a + b);
    else break;
  }
}

위 로직에 추가로 x, y가 1이 될 수 있으므로 1이면 항상 같은 수가 나오므로 한 번만 체크하고 반복문을 빠져나올 수 있게 예외처리해줘야한다.

 

시간복잡도는 O((logx bound) * (logy bound)).

---

소스코드 : github.com/fpdjsns/Algorithm/blob/master/leetcode/medium/970.%20Powerful%20Integers.cpp