%2021. 1. 26. 20:02에 작성된 글입니다% 2014번: 소수의 곱 첫째 줄에 K(1 ≤ K ≤ 100), N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 K개의 소수가 오름차순으로 주어진다. 같은 소수가 여러 번 주어지는 경우는 없으며, 주어지는 소수는 모두 541보다 작거나 www.acmicpc.net 1. priority queue로 \(N \log N\)컷. 2. 해가 \(2^{31}-1\)보다 작음이 보장됨. 3. 2 => 10 / 5 => 10. 중복 제거를 해야 함. 애초에 값을 넣을 때 중복되지 않도록 넣는 방법이 없을까?

\({\phi }^2={\phi }+1\)​ \(-1={\phi }-{\phi }^2\)​ \(P_n=F_n{\phi }+F_{n-1}\) \(=\large{\frac{{\phi }^{n+1}-\left(1-{\phi }\right)^n{\phi }}{\sqrt{5}}+\frac{{\phi }^{n-1}-\left(1-{\phi }\right)^{n-1}}{\sqrt{5}}}\) \(=\large{\frac{{\phi }^{n+1}-\left(1-{\phi }\right)^{n-1}\left({\phi }-{\phi }^2\right)+{\phi }^{n-1}-\left(1-{\phi }\right)^{n-1}}{\sqrt{5}}}\) \(=\large{\frac{{\phi }^{n+1}+\left(1-..

%2022. 1. 12. 01:05에 작성된 글입니다% 5615번: 아파트 임대 첫째 줄에 아파트의 면적의 수 N이 주어진다. 다음 줄부터 N개 줄에 카탈로그에 적혀있는 순서대로 면적이 주어진다. N은 100,000이하이고 면적은 231-1이하인 양의 정수이다. www.acmicpc.net 1. \(S = 2xy + x + y\) \(2S + 1 = ?\) 2. \(N = 100,000\)이고 시간 제한 1초. \(\log\) 수준의 시복도를 갖는 소수판정법 필요. 밀러-라빈! 남들은 인수분해 척척 했던 것 같은데 나는 S를 1부터 쭉 뿌리고 가능/불가능 본 뒤에 이거 소수 반토막 아님? 해서 알았다... 머리가 나빠서 컴퓨터가 고생함 ㅋㅋ

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

%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)\)을 제..

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) 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\)좌표 하나에 여러개의 점이 대응된다고 해보..

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