일단 태그에서부터 임의 정밀도/큰 수 연산이 붙어 있으니 고생 좀 해야 하겠다... 만! 이런 끔찍한 문제들은 보통 python의 Decimal로 해결한다. ​ c/cpp로 구현하는 것도 불가능한 건 아니고 실제로 적잖은 AC가 있긴 하다... 언제 따로 cpp bigint를 따로 구현해봐야겠다. ​ 꽤 높은 수준의 정밀도를 요구하는 문제기 때문에 기본적으로 지원하는 sin함수를 써서는 안 된다. 테일러 전개를 활용해 새로 함수를 짜야 한다. 파이 값도 중요해서 인터넷에서 몇백자리 긁어다 Decimal에 때려박았다. $Ax+B\sin x\ (A \geq B)$는 미분해서 보면 전체 구간에서 증가함을 알 수 있으므로 이분 탐색을 쓸 수 있다. Decimal로 잡고 st en mid 돌려가며 구했다. ​ 이..

%2021. 11. 9. 00:30에 작성된 글입니다% https://www.acmicpc.net/problem/19577 19577번: 수학은 재밌어 xφ(x) = n을 만족하는 양의 정수 x가 존재하면 최소의 x를, 존재하지 않으면 −1을 출력한다. www.acmicpc.net 오일러 피 함수라는 걸 여기서 처음 봤다. 대충 위키에서 본 내용에 따르면 이 함수는 아래의 성질을 갖는다고 한다. \(\gcd \left(a,b\right)=1\)일 때, \(\phi \left(ab\right)=\phi \left(a\right)\phi \left(b\right)\)​ \(\phi \left(p^n\right)=p^n\left(1-\frac{1}{p}\right)=p^{n-1}\left(p-1\right)\..

%2021. 11. 5. 14:39에 작성된 글입니다% https://www.acmicpc.net/problem/1007 1007번: 벡터 매칭 평면 상에 N개의 점이 찍혀있고, 그 점을 집합 P라고 하자. 집합 P의 벡터 매칭은 벡터의 집합인데, 모든 벡터는 집합 P의 한 점에서 시작해서, 또 다른 점에서 끝나는 벡터의 집합이다. 또, P에 속 www.acmicpc.net 풀어보려고 전부터 꽤 노력했는데 결국 고등학교 기하를 배우고 나서야 풀 수 있었다. 벡터의 성질을 맨바닥에서 끄집어낼 수준의 머리는 안 되는 모양이다. 주어진 점을 각각 \(P_1, P_2, P_3... P_n\)이라고 하자. 임의의 점 P를 하나 잡고, \(\overrightarrow{PP_1}, \overrightarrow{PP_..

%2021. 11. 5. 00:11에 작성된 글입니다% https://www.acmicpc.net/problem/6734 6734번: Radio direction finder A boat with a directional antenna can determine its present position with the help of readings from local beacons (radio transmitters). Each beacon is located at a known position and emits a unique signal. When a boat detects a signal, it rotates its anten www.acmicpc.net 평소에 Bronze 5 레이팅 문제는 시간 때우기..

%2021. 8. 22. 15:14에 작성된 글입니다% https://www.acmicpc.net/problem/1160 1160번: Random Number Generator 첫째 줄에 6개의 정수 m, a, c, X0, n, g (m, a, c, X0, n ≤ 1018, g ≤ 108)가 차례대로 주어진다. a, c, X0는 음이 아닌 정수이고 m, n, g는 양의 정수이다. www.acmicpc.net \(X_{n+1}=aX_n+c \mod M\) \(\mod M\)은 일단 나중에 계산하게 떼고 보면 다음과 같은 꼴이 된다. \(X_{n+1}=aX_n+c\)​ \(X_n\)의 일반항은 \(X_n=a^nX_0+c\left(1+a+...+a^{n-2}+a^{n-1}\right)\)​ 의 형태가 된다. ..

%2021. 6. 29. 02:35에 작성된 글입니다% https://www.acmicpc.net/problem/21094 21094번: Discrete Logarithm is a Joke $M = 10^{18} + 31$ is a prime number. $g = 42$ is a primitive root modulo $M$, which means that $g^{1} \bmod M, g^{2} \bmod M, \ldots, g^{M-1} \bmod M$ are all distinct integers from $[1; M)$. Let's define a function $f(x)$ as the smallest positive integer www.acmicpc.net 이산 로그 100만번 구하는건가보다..

%2020. 6. 13 01:07에 작성된 글입니다% https://www.acmicpc.net/problem/17105 17105번: 골드바흐 트리플 첫째 줄에 테스트 케이스의 개수 T (1 ≤ T ≤ 100,000)가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 N은 홀수이고, 5 < N ≤ 1,000,000을 만족한다. www.acmicpc.net 입력으로 들어오는 홀수는 \(N\)이고 큰 소수 \(p\)에 대해 다항함수 \( f, g, h \)를 \( f\left(x\right)=x^2+x^3+x^5+...+x^p\) \(g\left(x\right)=x^4+x^6+x^{10}+...+x^{2p}\) \( h\left(x\right)=x^6+x^9+x^{15}+...+x^{3p} \..

%2020. 3. 12. 22:14에 작성된 글입니다% https://www.acmicpc.net/problem/9012 9012번: 괄호 괄호 문자열(Parenthesis String, PS)은 두 개의 괄호 기호인 ‘(’ 와 ‘)’ 만으로 구성되어 있는 문자열이다. 그 중에서 괄호의 모양이 바르게 구성된 문자열을 올바른 괄호 문자열(Valid PS, VPS)이라고 www.acmicpc.net 여는 소괄호 닫는 소괄호 덕지덕지 붙인 문자열 주고 여는 것과 닫는 것이 제대로 맞아떨어졌는지 확인하는 문제. 문제의 알고리즘 분류는 스택으로 되어 있던데, 스택까지 안 써도 조금만 생각해 보면 간단하게 풀 수 있다. 여는 소괄호를 1, 닫는 소괄호를 -1로 치고 쭉 더한다. 만약 이 문자열이 Vaild PS라면..