오일러 피 함수 (2) 썸네일형 리스트형 [Python] 32228번 등차수열 만들기 https://www.acmicpc.net/problem/32228 24/09/15 맷코컵 당시 검수했던 문제 중 하나이다. 알면 보자마자 떠오르는 낚시 문제다. 문제 접근 방식: 문제에서는 주저리 주저리 적혀져 있는데, 오일러 파이 함수의 값을 출력하면 끝이다. 그러면, 결론이 왜 그렇게 나오는지에 대해 알아야 한다. 문제에서 주어진 것 처럼 mod $M$에서의 등차수열을 직접 구하는 방식으로 $K$값을 짜내려고 한다면 곤란하다. $N$의 제한과 $M$의 제한이 꽤나 크기 때문이다. $A_i$와 $M$이 서로소라는 조건, 모두 같은 $K$제곱을 하여 $A_{i}^{K}$로 만들고 mod $M$과 엮는다는 점을 유의깊게 생각하면 쉽게 파악할 수 있다. 이 $K$의 값이 $\varphi (M)$이 된다.. [Python] 30510번 토마에 함수 https://www.acmicpc.net/problem/30510 30510번: 토마에 함수 첫째 줄에 두 양의 정수 $P$, $Q$가 공백으로 구분되어 주어진다. $(1\le P\le Q\le 100\, 000)$ www.acmicpc.net 24/03/07 이전에 SASA컵을 검수한 적이 있었다. 사실 그때 너무 바빴어서 풀이만 생각하고 정해 코드를 짜지 않았었는데, 이 문제의 해설을 작성해보고자 한다. 문제 접근 방식: 문제를 요약하면 다음과 같다. $x$가 무리수면 $f(x) = 0$ $x$가 $0$이면 $f(x) = 1$ 그 외 $x = \frac{p}{q} ; \mathrm{gcd}(p, q) = 1$이면 $f(x) = \frac{1}{q}$ 임의의 유리수 $\frac{P}{Q}$가 주어질 .. 이전 1 다음