이 문제는 [BOJ 14862] 최대공약수 기댓값의 확장 버전이라고 할 수 있다. 최대공약수 기댓값 문제를 풀면서 klimmek55님의 코드를 보고 감명받아 이 문제를 푼 것이다. 굉장히 멋진 아이디어이니 참고하면 좋을 것 같다. 문제에서 주어진 코드는 다음과 같이 바꿔쓸 수 있다. \[\sum_{x_{1}=a_{1}}^{b_{1}}\sum_{x_{2}=a_{2}}^{b_{2}}...\sum_{x_{n}=a_{n}}^{b_{n}} \gcd(x_{1},x_{2},...,x_{n})\] 이런 경우에 Mobius inversion을 이용해서 다음과 같이 바꿔쓸 수 있다. (Mobius inversion 포스팅을 참고하라.) \[\sum_{k=1}^{\min(b_{1},b_{2},...,b{n})} \left(..

$a^{2}+b^{2} \equiv c^{2} \pmod{n}$을 만족하는 $(a,\ b,\ c)$($a \le b$) 쌍의 개수를 구하는 것이 목표이다. 집합 $\{s\}$를 1부터 $n-1$까지의 자연수의 제곱을 $n$으로 나눈 나머지의 집합이라 정의하자. 집합 $s$의 원소를 각 항의 차수로 하고 항의 계수가 1인 다항식 $P(x)$를 생각하자. e.g. $n=7$ 이면 $P(x)=2x+2x^{2}+2x^{4}$ $P(x)^{2}$를 했을 때 차수가 집합 $s$에 포함되어있는 것들의 계수를 전부 더하면 된다. 반면 문제의 조건에서 $a \le b$가 있다. 따라서 위 더한 값에서 $a=b$인 경우를 제외시킨 뒤 2로 나누고 $a=b$인 경우를 다시 더하면 된다. $a=b$인 경우는 $P(x)$의 차..

대부분 수학 문제라는 것이 함정 ㅋㅋ... 꾸준히 심어온 잔디에 빈칸이 생기는 슬픈 상황이 저번주에 발생했다. ㅜㅜ 스트릭 프리즈만 믿고 있었는데 알고보니 '적용하기'를 누르지 않았던 것...

어떤 홀수가 주어질 때 그 홀수를 세 개의 소수의 합으로 나타내는 방법이 얼마나 많은지 구하는 문제이다. 주어진 홀수를 $n$이라 하자. 그럼 경우는 3가지가 있다. 각 경우마다의 경우의 수를 $a, b, c$라고 두자. 1. $n=p+q+r$ 2. $n=2p+q$ 3. $n=3p$ 가장 쉽게 생각할 수 있는 것은 소수 차의 항만을 가지며 계수가 1인 다항식 $P(x)$를 생각할 수 있다. 이 $P(x)^{3}$에서 $x^n$의 계수가 우리가 구하고자 하는 답과 가장 유사할 것이다. 하지만 그 계수는 $6a+3b+c$가 된다. $c$는 쉽게 구할 수 있으나 $b$를 구하는 것이 어렵다. $b$는 $P(x)$에서 각 항의 차수만 2배가 된 식 $Q(x)$와 $P(x)$를 곱하게 된다면 $x^n$의 계수로 ..

다이아 새싹을 얻었다! 2022.2.24

함수 $f$는 다음과 같이 정의된다. \[f(a)=a^{N} \pmod{N}\] \[F_{1}(a)=f(a)\] \[F_{k+1}(a)=F_{k}(f(a)) (k=1,2,3,...)\] 이를 간단히 하면 다음과 같다. \[F_{k}(a)=a^{N^{k}} \pmod{N}\] 이때 $F_{k}(a)=a$인 최소의 $k$를 찾는 것이 우리의 목표이다. 먼저 $N=p$(소수)일 경우를 생각해보자. \[a^{N^{k}} \equiv a \pmod{N}\] 이때 $gcd(a,N)=1$이므로 \[a^{N^{k}-1} \equiv 1 \pmod{N}\] \[N^{k} \equiv 1 \pmod{\phi(N)}\] 만약 이때 $\gcd(N,\phi(N))=1$이 아니라면 만족하는 $k$가 존재하지 않는다. $k$가 존..