%2022. 1. 10. 21:27에 작성된 글입니다%
18507번: One Root
The only line of input contains two integers n and m (1 ≤ n, m ≤ 106, n ≥ 2).
www.acmicpc.net
\(x^n=ax+b\)
주어지는 2 이상의 \(n\)에 대하여, 방정식의 해가 오직 하나가 되도록 하는 abs가 \(m\) 이하인 정수 \(a, b\) 쌍을 모두 구하는 문제다. 고등학교 3년 동안 지겹도록 본 꼴이라 접근은 어렵지 않았다.
우선 \(n\)이 짝수일 때와 홀수일 때로 나누어야 한다. 그래프 개형이 달라지기 때문.
---
만약 \(n\)이 짝수라면, 방정식의 해가 오직 하나가 되기 위해서는 \(ax+b\)가 \(x^n\)에 접해야 한다.
기울기가 양수인 부분과 음수인 부분은 대칭이니까 양의 부분을 고려한 뒤 두 배를 해 주고, \(a=b=0\)에 더해서 총 경우를 계산할 수 있다.
(만약 순서쌍 \((a, b)\)가 조건을 만족한다면, 순서쌍 \((-a, b)\) 또한 조건을 만족한다)
양수인 기울기 \(a\)에 대해서 \(y\) 절편 \(b\)를 표현해 보자. \(ax+b\)와 \(x^n\)의 접점 \(P(p, q)\)에 대하여...
\(q=p^n=aq+b\)
\(np^{n-1}=a\)
\(p=\left(\frac{a}{n}\right)^{\frac{1}{n-1}}\)
\(\left(\frac{a}{n}\right)^{\frac{n}{n-1}}=a\left(\frac{a}{n}\right)^{\frac{1}{n-1}}+b\)
\(b=a\left(\frac{1}{n}-1\right)\left(\frac{a}{n}\right)^{\frac{1}{n-1}}\)
그러므로 한 정수인 기울기 \(a\)에 대하여 조건을 만족하는 \(b\)가 존재하는지 확인하려면
\(a\left(\frac{1}{n}-1\right)\left(\frac{a}{n}\right)^{\frac{1}{n-1}}\)
가 범위 내의 정수가 되는지를 확인하면 된다. 이 값이 정수가 되기 위해서는 임의의 자연수 \(k\)에 대하여
\(a=k^{n-1}n\)
이면 되는데, 이를 그대로 식에 대입해 보면
\(b=k^n\left(1-n\right)\)
이 나온다. 이제 \(k\)를 1부터 쭉 올리면서 \(a\)와 \(b\)를 구하고 범위 내라면 \(count\)++, 최종적으로 \(2\cdot count+1\)을 출력하면 된다.
---
이제 \(n\)이 홀수인 경우를 보자. 여기서도 탐색 범위를 줄일 수 있는데, 우선 \(a\)가 음의 정수 혹은 \(0\)일 때부터 보자.
홀수인 \(n\)에 대하여 \(x^n\)은 전 구간에서 증가함수이므로 \(a\)가 음수나 \(0\)인 경우에 \(ax+b\)와 \(x^n\)은 오직 한 점에서만 만난다. 그러므로 모든 \(b\)(\(2M+1\)개) \(\cdot\) \(a \leq 0\)인 \(a\)(\(M+1\)개), \((2M+1)(M+1)\)은 기본적으로 세고 들어가면 된다.
이제 까다로운 부분은 \(a>0\)인 경우인데, 조건을 만족하는 \((a, b)\)에 대하여 \((a, -b)\) 또한 조건을 만족시키므로 \(b\)가 음수인 부분만 살펴 두 배를 해 주자.
\(a > 0, b < 0\)이고, \(ax+b\)가 \(x^n\)에 접하는 상황을 생각해 보자. \(x^n\)의 개형에 따라, \(ax+b\)는 \(x^n\) 과의 접점 말고도 한 개의 해를 더 가질 것이다.
이 상황에서 \(b\)만 살짝 올리면 해는 세 개가 되고, 내리면 해는 한 개가 된다.
따라서 우리는 \(a\)를 쭉 돌면서 \(x^n\)과 접하는 \(ax+b\)에서의 \(b\) 값을 구하고, \(b\)보다 작으면서 \(-m\)보다 크거나 같은 모든 정수의 수를 다 세서 더해준 뒤 두 배를 해 \((2M+1)(M+1)\)과 더해서 출력하면 답을 얻을 수 있다!
이때 \(b\)의 참값이 딱 정수가 되는 경우 부동소수점 이슈 때문에 판정을 잘못할 수 있다.
\(n\)이 짝수일 때 보았듯 \(a=nk^{n-1}\)일 때는 \(b\)가 정수가 되기 때문에 저 경우만 따로 빼서 처리하면 문제없이 풀 수 있다.
나는 이상한 곳에서 실수하는 바람에 자그마치 80회에 육박하는 제출을 기록하고 정답을 받았다. 혼자 정답 비율 다 깎아먹음. 부끄럽네 ㅋㅋ;;