kjk9704   1년 전

우선 1699번(제곱수의 합)은 DP로도 풀 수 있으나 아래의 공식 3가지를 응용하면 AC 받을 수 있습니다.

# 라그랑주의 네 제곱수 정리 : https://en.wikipedia.org/wiki/Lagrange%27s_four-square_theorem

# 르장드르의 세 제곱수 정리 : https://en.wikipedia.org/wiki/Legendre%27s_three-square_theorem

# 페르마의 두 제곱수 정리 : https://en.wikipedia.org/wiki/Fermat%27s_theorem_on_sums_of_two_squares

그 다음 1699번 문제를 위 3가지 공식을 응용해서 풀었다면 그 다음 4149번(큰 수 소인수분해) 문제를 해결합니다.

4149번(큰 수 소인수분해)는 gcd(n, k) = 1(13926번)에도 쓰이니 중요한 문제입니다.

그 뒤 1699번 소스 코드와 4149번 소스 코드를 적당히 혼합해서 구현하면 AC 받을 수 있습니다.

마지막으로 이 문제의 예시들을 공유합니다.

zenith82114   1년 전

관련된 문제의 번호를 적는 것만으로 스포일러가 될 수 있으므로 제목이 아닌 본문에 써주시면 좋겠습니다.

kjk9704   1년 전

수정했습니다.

댓글을 작성하려면 로그인해야 합니다.