PS | CP

[18507] One Root

%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\)에 접해야 한다. ..

[23894] 합성함수와 쿼리 2

%2022. 1. 9. 00:06에 작성된 글입니다% 23894번: 합성함수와 쿼리 2 함수 $f : \{1, 2, \cdots, N\} → \{1, 2, \cdots, N\}$의 각각의 함숫값 $f(1), f(2), \cdots, f(N)$이 주어진다. 이 때, 다음 쿼리를 수행하는 프로그램을 작성하시오. 1 x : $f(1)$의 값을 $x$로 변경한다. 2 m x : $f^m (x www.acmicpc.net 여행 갔을 때 호텔에서 풀려고 잡았던 문제. 취한 상태였기 때문에 WA만 잔뜩 내고 집에 돌아와서 마저 풀었다. 쿼리 꼴 보면 sparse table 생각이 난다. 2번 쿼리는 어지간하면 \(O(\log m)\)으로 처리 가능하다는 얘기인데, 문제는 1번 쿼리. 1번 쿼리는 \(f(1)\)을 제..

[14347] Radioactive Islands (Large)

https://blog.safespot.dev/entry/14346-Radioactive-Islands-Small의 후속 문제. 거의 모든 해설은 저기 다 있고, 일단 N 상한만 2로 늘어난 상황이기 때문에 N=2인 경우에 대해서 식을 세우면 $\displaystyle \int _{-10}^{10}\left(1+\frac{1}{x^2+\left\{y\left(x\right)-c_1\right\}^2}+\frac{1}{x^2+\left\{y\left(x\right)-c_2\right\}^2}\right)\sqrt{1+\left\{y^{\prime}\left(x\right)\right\}^2}dx$ 를 최소화해야 하는 상황. 똑같이 범함수 만들면 $\displaystyle f\left(y,\ y^{\prim..

[14346] Radioactive Islands (Small)

14346번: Radioactive Islands (Small) The first line of the input gives the number of test cases, T; T test cases follow. Each test cases consists of two lines. The first line of a test case consists of three values: an integer N, and two floating-point numbers A and B, as described in www.acmicpc.net 일단 배의 궤적은 함수로 나타낼 수 있다. 말인즉슨, 궤적은 \(x\) 좌표 하나에 한 개의 점만 대응된다는 뜻이다. 만약 \(x\)좌표 하나에 여러개의 점이 대응된다고 해보..

[16136] 준하의 정수론 과제 (Divmaster)

%2021. 12. 6. 05:11에 작성된 글입니다% 16136번: 준하의 정수론 과제 (Divmaster) 준하는 3학년 2학기 때 들으려고 했던 정수론을 수강신청을 잘못하는 바람에 2학년 1학기 때 신청하고 말았다! 사악한 정수론 선생님은 자연수의 약수의 개수를 구하는 문제를 던지고, 이 문제 www.acmicpc.net Divmaster가 무슨 뜻일까? 해당 div에서 가장 어려운 문제였다는 말일까? 아무튼 쿼리 처리하는 문제다. 쿼리 모양새를 보니 세그트리를 쓰면 좋을 것 같다. 일단 에라토스테네스의 체를 약간 응용해서 \(1\)~\(10^6\)까지 약수의 개수를 구할 수 있다. 이거 어디 담아놓고서 나중에 필요할 때 꺼내먹으면 된다. 노드는 구간의 합과 died라는 이름의 bool 변수를 갖게..

[4357] 이산 로그

%2021. 12. 5. 23:18에 작성된 글입니다% 4357번: 이산 로그 소수 P(2 ≤ P < 231), 정수 B(2 ≤ B < P), 정수 N(1 ≤ N < P)가 주어졌을 때, 밑을 B, 나머지를 P로 하는 N의 이산 로그를 구하는 프로그램을 작성하시오. 즉, 다음과 같은 조건을 만족하는 정수 L을 찾으 www.acmicpc.net \(B^L\equiv N\mod P\)​ 를 만족시키는 \(L\)을 찾자. Babystep Giantstep으로도 알려진 Shanks’ Algorithm을 사용하면 된다. \(L=ax+b\)​ \(B^{ax+b}\equiv N\mod P\)​ \(B^{ax}\equiv B^{-b}N\mod P\)​ 페르마의 소정리에 따라 \(B^{-1}\equiv B^{P-2}\m..

[2261] 가장 가까운 두 점

%2021. 12. 3. 10:13에 작성된 글입니다% 2261번: 가장 가까운 두 점 첫째 줄에 자연수 n(2 ≤ n ≤ 100,000)이 주어진다. 다음 n개의 줄에는 차례로 각 점의 x, y좌표가 주어진다. 각각의 좌표는 절댓값이 10,000을 넘지 않는 정수이다. 여러 점이 같은 좌표를 가질 수도 www.acmicpc.net 분할 정복의 대표적인 예제로 많이 쓰이는 문제인 것 같던데 스위핑으로 푸는 게 아이디어 잡기도 구현도 훨씬 나은 듯. 약간의 데이터 처리와 이분 탐색 스위핑으로 그냥 풀린다. 분할 정복으로 풀면 P2-P1일지도 모르겠는데 스위핑으로 풀면 P2-P1 수준까지는 아닌듯... 내가 스위핑으로 풀었으니까 여기에는 스위핑 풀이 적음 ​ 전반적인 흐름: x 값이 작은 점부터 큰 점까지 ..

[2595] 배수

%2021. 12. 1. 22:47에 작성된 글입니다% 2595번: 배수 N은 30,000이하의 자연수이다. www.acmicpc.net 05KOI 지역본선 고등부 5번이랜다... 뻘짓을 좀 하긴 했는데 여튼 푸는 데만 거의 3시간을 갖다 박았으니 아직 KOI 지역 수준에도 못 미치는 것이다. 안타깝다. ​ 문제를 푸는 데 중요한 사실은, 조건을 만족하는 출력은 모두 숫자의 종류의 수(이하 cnt(x)로 씀)가 1 혹은 2라는 것이다. 증명은 모르겠다. ​ 1인 경우에는 당연히 1111, 33333333, 77777 따위의 수가 될 것이고, 2는 3333300000000, 44444440, 20220222220, 2882828, 5555555550 뭐 이런 식의 형태이다. ​ 1. 수에 10의 배수가 있..