1월 PS/수학일지(Ft. HLD Recursive DP)

 앞으로 큰 목적 없이 문제를 풀거나 공부하게 될 것 같은데, 공부한 것들의 발자취를 남기는 것이 좋을 것 같아서 월별로 일지를 작성하기로 했다. 큰 감흥이 없는 문제는 제외하고, 최대한 배운 것이 있는 문제만 기술하였다.

 

1. PS

ABC 317 Ex-Walk

Ex - Walk

 해결하지 못하고 에디토리얼을 깠다.

 

 그냥 dp[i][j]를 i개의 간선을 거친 뒤 j번 위치에 존재하는 가짓수라고 하면 O(nk)에는 문제를 풀 수 있지만 자명하게도 너무 느리다.

 

 먼저, 1로 가는 간선이 하나도 없는 경우를 생각하자.

 

 보통 이런 상황에서는 생성함수적인 표현을 생각하는 것이 이득이 될 때가 많다. \(F_v(x)\) 를, v번 정점에 도달하는 가짓수를 거친 간선의 개수에 따라 표현한 다항식이라고 하자. 그렇다면 다음과 같은 간단한 식이 성립한다:

$$ F_v=[A_v=1]xF_v+[B_{v-1}=1]xF_{v-1}+[C_{v-2}=1]xF_{v-2} $$

 

 따라서 \( P_v(x)=1/(1-x[A_v=1]), Q_v(x)=x[B_{v-1}=1], R_v(x)=x[C_{v-2}=1]  \)과 같이 두고 나면, \( F_v(x)=P_v(x)Q_v(x)F_{v-1}+P_v(x)R_v(x)F_{v-2} \)와 같이 나타남을 알 수 있다. 따라서 F를 적당한 P,Q,R들의 행렬곱의 형태로 만들 수 있고, 총 n개 정도의 행렬들을 분할정복하여 전부 곱해주면 F_n을 얻을 수 있다.

 

 1로 가는 간선이 존재하는 경우에는 추가적으로 고려할 것이 생긴다. 1에서 출발해서, 중간 과정동안 한 번도 1을 밟지 않고 마지막에 1로 다시 돌아오는 가짓수의 생성함수는 결국 \( x\sum_{i=1}^N D_iF_i \)와 같이 나타날 것임을 알 수 있다. 이에 착안하여 \( G_v(x)=\sum_{i=1}^n D_iF_i \)와 같이 정의하면 구하고자 하는 값이 \( G_N \)일 것임을 알 수 있다. 이를 알게 된다면, 결국 답은 \( F_N/(1-xG_N) \)의 k번째 항을 구하는 것으로 환원된다. 위의 경우와 같이 점화식을 세워보면 다항식을 원소로 하는 3*3 행렬곱으로 표현됨을 확인가능하여, 이를 기반으로 구현하면 된다.

 

ABC 311 Ex-Many Illumination Plans

Ex - Many Illumination Plans

해당 문제는 "HLD Recursive DP"라는 테크닉을 응용하여 해결될 수 있다. 해당 글을 주로 참조하였다. 필자는 해당 글보다 더욱 좋은 설명을 제시할 자신이 없기 때문에, 그냥 직관적으로 이런 풀이를 왜 떠올려야 하는지를 중점적으로 설명하겠다. https://infossm.github.io/blog/2023/08/20/HLRecDP/ 

 

나이브한 접근으로는 O(NX^2)의 풀이가 쉽게 나올 수 있지만, 이보다 시간복잡도를 줄이는 것은 쉽지 않다.

 

이미 채워져있는 두 DP테이블을 합치는 것으로부터 O(X^2)의 복잡도가 기원한다는 것을 관찰할 수 있다. 따라서, 만약 효율적인 풀이가 존재한다면 이는 이러한 두 DP테이블이 합쳐지는 것을 최대한 피하는 방향이어야 할 것이다.

 

만약 DFS(v,dp)를, 초기에 dp라는 일련의 냅색의 상태가 주어졌을 때 v 이하의 서브트리들에서 주어진 조건을 만족하며 골라서 얻을 수 있는 개량된 냅색의 결과를 반환하는 함수로 정의한다면 어떻게 될까? DFS 한번의 호출에서 결괏값을 계산하기 위해선, 내부적으로 자식들의 DFS함수를 두 번씩 호출하는 방식으로 답을 계산 가능함을 확인가능하다. 물론 이러한 방식은 O(2^N*X)로, 과하게 비효율적임을 알 수 있다.

 

 한 가지 중요한 관찰은, DFS 함수에서 자식으로의 DFS를 맨 처음 호출할 때에는 한 번만 호출해도 필요한 정보를 전부 얻을 수 있다는 점이다. 따라서 "단 하나의" 자식에 대해서는, DFS를 한 번만 호출해도 된다. 일반적으로 깊이가 깊어질수록 DFS의 호출량이 지수적으로 증가하기 때문에, Heavy Chain부터 탐색하는 것이 직관적으로 이득이 될 것으로 예상가능하다. 실제로 복잡도 분석을 해보면 O(N^{log_2(3)}X)에 문제가 해결된다.

 

물론, 해당 문제는 모든 서브트리에 대한 답을 찾아야 하고, 이를 위해서는 추가적인 최적화가 필요하다. 이는 DFS 함수에, 해당 서브트리에 존재하는 모든 정점에 대해 답을 찾을 것인가 하는 find_all 인자를 추가하여 복잡도를 잘 분석해보면 여전히 같은 시간복잡도로 문제가 풀림을 관찰할 수 있다. 

 

디테일이 관심있다면 첨부한 글을 읽을 것을 권고한다.

 

ABC 310 Ex-Negative Cost

Ex - Negative Cost

역시 풀진 못했고 풀이를 봤다.

 

해당 문제를 가장 어렵게 만드는 주범은 코스트 조건이다. 본 풀이에서는 이러한 제약을 놀랍게 해결하고, 간단한 냅색 문제로 환원한다. 이는 다음과 같은 강력한 Claim을 기반으로 한다. 참고로, 코스트는 그냥 부호를 뒤집어서 C가 양수이면 증가하고 음수이면 감소하는 것으로 한다.

 

Definition. 어떤 연산들의 열 A_1,A_2,...,A_k가 "기본수열"이라는 것은, 해당 연산을 시행하면서 코스트가 항상 0 이상 2L 미만으로 유지된다는 것이다. 이때, L은 편의상 300이다.

 

Claim) 모든 올바른 연산들의 열에 대해서, 해당 열과 동일한 길이를 가지고 동일한 데미지를 입히는 수열이 존재하며, 해당 수열은 기본열들로 분해될 수 있다. 즉, 기본열들의 결합만을 생각해도 각 길이별로 모든 데미지를 고려할 수 있다.

 

pf) 현재까지 더한 값이 L 이상인데, 뒤에 차례대로 코스트가 양수인 연산과 음수인 연산을 하는 인덱스가 존재한다면, 그 두 연산을 바꿔주자. 이러한 교환이 정당함은 자명하다. 이러한 연산을 할 수 있을 때까지 반복한 경우를 생각하자. 이러한 결과물을 \( B_1,...,B_k \)와 같이 쓰자. 코스트가 음수인 가장 큰 인덱스를 q라고 하면, 해당 수열은 \( B_1,...,B_q \)와 같은 기본열과, 그 뒤로 오는 길이 1짜리 기본열들로 분해된다.

 

심지어 존재하는 모든 기본열들은 길이 2L 이하의 기본열들의 조합과 동등하다(즉, 같은 길이와 데미지를 가진다).

 

pf) 길이에 대한 귀납법을 사용하자. 어떤 열 A의 길이가 2L+1 이하라면, \( 1\le p<q\le 2L+1 \)이 존재해서 \( C_{A_1}+...+C_{A_p}=C_{A_1}+...+C_{A_q} \)이도록 할 수 있음이 비둘기집 원리에 의해 증명될 수 있다. 이제 A를 두 부분열 \( [A_1A_2...A_pA_{q+1}A_{q+2}...A_{len}], [A_{p+1}...A_q] \)와 같이 쪼개자. 앞의 것은 올바른 기본열이기 때문에 귀납법을 적용하여 쪼갤 수 있다. 후자의 경우에는 C가 큰 순서대로 정렬해서 올바르게 변경해주고나면, 이는 결국 위의 claim에 의해서 기본열로 분해될 수 있음을 알 수 있다. 따라서 전체 수열이 길이 2L 이하의 기본열들로 분해될 수 있다.

 

결국 이제 문제는 길이 2L 이하의 기본열들만을 활용하여 값 H를 넘길 수 있는 최소 길이를 찾는 것이 된다. 기본열들의 결합은 항상 올바르며, 심지어 올바른 열들의 결합 또한 올바르기 때문에 이제 코스트를 신경쓸 필요가 없다.

 

이는 간단한 냅색문제로 환원되고, 이는 어렵지 않게 해결될 수 있다.

 

BOJ 19558 Joker

Queue-Undo Trick의 간단한 연습문제. 트릭 자체는 무척 흥미로웠다.

BOJ 1868 보물찾기 

Shallowest Decomposition Tree의 정의 자체이다.

BOJ 2534 카드배열

우선 제곱 풀이부터 생각하는 것이 바람직하다. 가장 직관적인 제곱 풀이는 DAG를 만든 다음, 큰 자릿수부터 보면서 해당 자릿수보다 커야 하며 아직 안 채워진 위치의 개수를 센 다음, 남아있는 수 중에서 그러한 위치들을 위한 것들을 제외한 가장 큰 수를 넣는 것이다.

 

필자는 가장 큰 수 부터 가장 큰 자릿수에 넣으면 될 것이라고 생각했는데, 이는 적당히 큰 자릿수에 큰 값을 넣기 위해 초반에 제일 큰 수를 작은 위치에 넣고 희생하는 것을 포착하지 못해서 잘 작동하지 않았다.

 

올바른 그리디는 작은 수를 가장 작은 자릿수부터 채워넣는 것인듯하다. 이렇게 할 경우 큰 자릿수는 다른 모든 소모가능한 안전장치가 소모된 이후 비로소 할당될 수 있는 최대한 큰 수가 채워넣어지게 되어, 위의 제곱풀이와 동일한 작동을 한다...고 생각했다.

2. 수학

최근에는 몇가지 수올 문제들을 좀 풀면서 수학적 감을 재활하고자 하는데, 동기부여가 잘 되지 않아 많이 하지는 못하였다. 그래도 이제 일지를 작성하니까 많이 풀게 되지 않을까?

 

2016 IMO SL A1 

가장 직관적인 풀이는 \( f(x)=log(1+x^2) \)가 convex함을 보인 다음, 젠센 부등식을 사용하는 것이다.

2016 IMO SL A6 

물론, 양쪽이 동일한 항을 가져선 안되기 때문에 적어도 2016개의 수는 지워야 한다.

 

이제 2016개의 수를 지우면 됨을 증명하겠다. 왼쪽에는 \( x-(4k+1), x-(4k) \)꼴의 항만을 남겨놓고, 오른쪽에는 그렇지 않은 항들을 남겨둔다.

 

다음과 같은 1008개의 부등식을 생각하자: $$ (x-1)(x-4)<(x-2)(x-3) $$ $$ ... $$ $$ (x-2013)(x-2016)<(x-2014)(x-2015) $$

 

만약 이 부등식들의 2016(각 부등식 하나마다 2개의 항씩, 총 1008개의 부등식으로부터)개의 모든 항이 양수라면, 아무런 걱정을 할 필요가 없다. 항상 오른쪽 항이 더욱 클 것이다.

 

만약 2016개의 항 중 정확히 하나가 음수라면, 그러한 항은 왼쪽에 있을 것이기 때문에 이번에도 오른쪽 항들의 곱이 더 크다.

 

따라서 유일하게 문제가 될 수 있는 케이스는, 어떤 m에 대해서 \( (x-(4m+4))(x-(4m+1)), (x-(4m+2))(x-(4m+3))<0 \)인 경우이다. 중요한 것은, 이 경우 두 항의 비율 차이가 9 이상이라는 것이다. 따라서 나머지 항들에 의한 비율의 변화가 9보다 클 수 없음을 증명하는 방향으로 생각할 수 있다.

 

다음과 같은 claim이 성립한다.

 

Claim. \( \prod_{k=0}^\infty \frac{(4k+2+a)(4k+3+a)}{(4k+1+a)(4k+4+a)}<e \) for all \( a\ge 0 \)

 

pf) a=0일때만 보이면 충분하다. a가 클 수록 분자와 분모의 비율차이가 희석되기 때문이다. 이 경우 전체에 log를 씌우고 나면, \( \sum_{k=0} \log(1+\frac{2}{(4k+1)(4k+4)})<1 \)임을 증명하는 문제가 된다. log의 간단한 근사에 따르면 좌변은 \( \sum_{k=0} \frac{2}{(4k+1)(4k+4)} \) 이하이고, 해당 term은 자명하게도 \( \frac{\pi^2}{12} \) 이하이므로, 증명이 끝난다.

 

이제 다시 원래 문제로 돌아오자. 이미 m에 대한 부등식으로부터, 왼쪽이 오른쪽보다 절댓값상 9배 이상 큼을 안다. 한편, m을 기준으로 왼쪽과 오른쪽에 있는 항들로부터 오는 비율차이는, Claim에 의해 오른쪽이 왼쪽보다 많아야 \(e^2\)배 크다. 따라서 왼쪽의 절댓값이 오른쪽보다 크고, 둘 다 부호가 음수이므로 결국 오른쪽이 항상 더 크다.

2016 IMO SL N5

펠 방정식 이론을 잘 활용해야 하는 문제이다. 주어진 식을 정리하면 \( (k-1)x^2-ky^2=-a \)와 같은 식이 되고, 이를 만족하는 (x,y) 순서쌍에 대한 분석은 이미 잘 이루어져 있다. 

 

펠 방정식 이론에 따라, 다음의 사실이 성립한다:

 

\( (x,y) \)가 해라면, \( ((2k-1)x+2ky,(2k-1)y+2(k-1)x) \) 또한 해가 된다.

 

x,y 둘 다 음이 아니도록 할 수 있기 때문에, 해당 연산을 충분히 진행하고 나면 x의 절댓값은 충분히 커지게 된다. 따라서 \( B\subset A \)는 어렵지 않게 보일 수 있다.

 

다음과 같은 사실 또한 성립한다:

 

\( (x,y) \)가 해라면, \( ((2k-1)x-2ky,(2k-1)y-2(k-1)x) \) 또한 해이다.

 

이제 sqrt(a) 이상의 x를 사용하는 해를 가지고 있다고 하자. 그렇다면 x,y에 대한 적절한 대소관계를 활용해 생성된 해가 충분히 작아짐을 보여야 할 것이다. 생성된 해를 x',y'라고 하자.

 

\( x>\sqrt{a} \)이기 때문에 x>y이고, \( y'((2k-1)y+2(k-1)x)=(2k-1)^2y^2-4(k-1)^2x^2=4(k-1)+y^2>0 \)으로부터 \( y'>0 \)임을 얻는다.

 

\( x'<0 \)이 될 조건은 \( x^2<4k \)이거나, \( (2k-1)^2x^2<4k^2y^2 \)임을 보일 수 있다. 만약 \( x'>0 \)이라면, \( x'+y'=x-y<x \)이고, 자연스럽게 \(x'<x  \)가 된다. 따라서 \( x<\sqrt{4k}\)나 \( x<y \)중 하나가 성립하기 전까지 위의 공정을 거쳐 x를 최대한 줄인다.

 

만약 \( x<y \)라면 이는 그 자체로 \( x<\sqrt{a} \)임을 의미하므로, 증명이 끝난다.

 

그렇지 않은 경우에는 새로 생성한 x'는 음수가 될 것이므로, \(x'+y'=|y'|-|x'|=x-y>0 \)이 된다. 따라서 \( |y'|>|x'| \)가 성립하고, 따라서 \( x<\sqrt{a} \)인 해를 얻는다. 이는 \( A\subset B \)임을 의미한다.

 

결과적으로, A=B이다.

Iran RMM TST 2020

(a,b,c) 형태의 triple을 직접 세는 데에는 큰 애로사항이 따른다. 따라서, 대칭성으로부터 오는 parity의 차이를 이용하기 위해 다음의 조건을 만족하는 튜플의 개수를 셀 것이다:

 

\( 0<a,b,c,d<\sqrt{p}, p=ad+bc \)

 

그러한 조건을 만족하는 튜플의 집합을 \( S_p \)라고 하자. 추가로, \( R_p=\left{ (a,b)|0<a,b<\sqrt{p}, gcd(a,b)=1 \right\} \)과 같이 두자.

 

\( f:R_p\to \left\{ 1,2,...,p-1 \right\} \)을 \( f((a,b))=a(modp)/b(modp) \)와 같이 정의하자. 이러한 함수가 일대일임을 알 수 있는데, \( ad=bc(mod p) \)라면 각 수들이 sqrt p 미만이라는 점으로부터 사실 ad=bc임을 알 수 있고, a,b의 서로소 조건때문에 a의 모든 인자를 c가 전부 가져야 하고, 그 반대도 성립하기 때문이다.

 

한편, Thue's Lemma 에 따르면 \( \left\{ 1,2,...,p-1 \right\} =f(R_p)\cup f(-R_p) \)가 성립한다. 또한, \( f(R_p) \)와 \( f(-R_p)\)의 교집합에 존재하는 원소 (a,b)와 (c,d)에 대해서 \( ad+bc=p \)가 성립함에 주목하라.

 

따라서 이제 \( S_p \)의 크기를 estimate할 수 있는 좋은 상황이 되었다. 이는 사실 \( 2|R_p|-(p-1) \)이라는 것이다.

 

\( R_p\)의 크기는 간단한 정수론적 지식을 동원하면 \( 2(\phi(1)+...+\phi([\sqrt{p}]))-1 \)이다.

 

이제 \( S_p \)에 속하는 쌍들의 대칭성을 분석하자. 만약 a,b,c,d가 전부 다르다면, 그러한 쌍들은 총 8가지 가짓수로 세어질 수 있다: \( (a,b,c,d),(b,a,c,d),(a,b,d,c),(b,a,d,c),(c,d,a,b),(d,c,a,b),(c,d,b,a),(d,c,b,a) \)

 

만약 a=d라면 그러한 쌍은 \( (a,a,b,c),(a,a,c,b),(b,c,a,a),(c,b,a,a) \)로 4쌍이 존재한다.

 

a=d,c=b인 경우는 2가지 가짓수가 존재한다.

 

일단 p가 mod8에 대해 3인 경우부터 생각해보면, a=d,c=b인 경우는 생각할 필요가 없을 것이다. 따라서 결국 \( |S_p|=4(\phi(1)+\phi(2)+...+\phi([\sqrt{p}]))-p-1\equiv 4(mod 8) \)임을 얻게 되어, 기존에 세고자 했던 것이 홀수개임이 증명된다.

 

p가 mod8에 대해 1인 경우 \( a^2+b^2=p \)을 만족하는 a,b의 쌍은 정확히 2개 존재함이 알려져 있다(페르마 두 제곱수 정리에 의해 존재하며, 뒤집기에 대해 유일함은 가우스 정수가 UFD임으로부터 유도된다). 이 경우 \( |S_p|\equiv 6(mod 8) \)이기 때문에, 여전히 증명하고자 하는 바가 성립한다.

 

2016 IMO SL A8 

일단, 답은 \( a=4/9 \)이다. 

 

x들의 차이에 대한 부등식으로 생각하는 대신, \( y_i=x_i-x_{i-1} \)로 두어 \( \frac{1}{y_1}+\cdots +\frac{1}{y_n}\ge a(\frac{2}{y_1}+\frac{3}{y_1+y_2}+\cdots+\frac{n+1}{y_1+\cdots+y_n}) \)으로 바꾸자. 4/9보다 늘릴 수 없는 이유는 \( x_k=\frac{k(k+1)(k+2)}{3} \)인 경우를 생각하면 된다.

 

이제 이것이 최선임을 보이자.

 

\( \frac{k^2}{a}+\frac{9}{b}\ge \frac{(k+3)^2}{a+b} \)가 성립한다. 정리해보면 \( k^2b(a+b)+9a(a+b)-(k+3)^2ab=k^2b^2+9a^2-6kab\ge 0 \)이기 때문이다.(이는 Titu's Lemma의 특수한 경우이다.)

 

따라서 다음의 식들이 성립한다: $$ 9/y_1\ge 9/y_1 $$ $$ 1/y_1+9/y_2\ge 16/(y_1+y_2) $$ $$ 4/(y_1+y_2)+9/y_3\ge 25/(y_1+y_2+y_3) $$ $$ \cdots $$ $$ (n-1)^2/(y_1+\cdots+y_{n-1})+9/y_n\ge (n+2)^2/(y_1+\cdots+y_n) $$

 

이들을 전부 더하면 원하는 부등식이 된다.

 

풀이는 그리 복잡하지 않지만, 개인적으로 이러한 풀이를 발상하는 것은 상당히 어렵다고 생각한다. 일단 최적의 a를 찾는것도 쉽지 않고, 추론을 하고나서도 이것보다 큰 경우가 존재하지 않을 것이라고 확신하는 것이 쉽지 않기 때문이다.

 

풀이의 추론에 대해서 몇가지 말해보자면, n=1일때의 최적은 a=1/2이고, n=2인 경우 a=12/25임을 얻을 수 있다. 이로부터 a가 0.4x 근처의 무언가임을 추론할 수 있다.

 

그 외에도 주어진 상황이 Titu's lemma의 전형적인 모양과 비슷하다는 점으로부터 titu's lemma에 나오는 꼴들을 텔레스코핑하듯이 합쳐서 원하는 모양을 만들고 싶다는 생각을 할 수 있으며, 이로부터 계수조정을 하는 방향으로도 풀이가 진행될 수 있을 것 같다.

2016 IMO SL N6 

직관적으로 \( f(x)=x^2 \)이 유일한 함수여야만 할 것 같다.

 

일단 m=n=1을 대입해보면, f(1)=1임을 얻는다. 그 외에도 중요한 대입결과는 다음과 같다:

 

\( P(1,n): f(n)|1+nf(n) \)

 

\( P(n,n):2f(n)-n^2|2nf(n)\to 2f(n)-n^2|n^3 \)

 

두 번째 식에서 좌변이 n^3을 나눈다는 것은, n=p일때 매우 강력한 효과를 발휘할 수 있을 것으로 보인다. 이 경우 \( 2f(p)-p^2 \)은 \( 1,p,p^2,p^3 \)중 하나가 된다. 이제 목표는 해당 값이 p^2일수밖에 없음을 보이는 것이 될 것이다. 추가로 p가 원하는 만큼 큰 경우를 분석하자.

 

Case 1: \( f(p)=1 \)

p-2는 p+1를 나누지 않는다(p가 아주 크다면).

 

Case 2: \( f(p)=p \)

p,p를 대입하면, 2p-p^2가 p^3을 나눠야 하는데, p-2는 p를 나눌 수 없다.

 

Case 3: \( f(p)=p^3 \)

역시 p^2(2p-1)이 p^3을 나눠야 하는데, 크기부터 불가능하다.

 

따라서 \(f(p)=p^2\)이다.

 

이제 임의의 정수 n과, 그에 비해 매우 큰 소수 p를 생각하자.

 

\( P(n,p): p^2-np+f(n)|p^3+nf(n) \)이 성립해야 한다. 이를 살짝 바꾸면, \( p^2-np+f(n)|p^3-np^2+n^2p \)가 성립해야 한다.

p가 충분히 크다면, 좌변이 p의 배수가 되는 것은 불가능하다. f(n)은 고정되어있기 때문이다. 따라서 추가적으로, \( p^2-np+f(n)|p^2-np+n^2\to p^2-np+f^n|n^2-f(n) \)가 성립해야 한다. 이것이 모든 p에 대해 성립할 방법은, \(f(n)=n^2 \)뿐이다. 따라서 보이고자 하는 바가 증명되었다.

출처 불명

If we denote \(S_n\) be the set of integers representible in the form \(x^2+ny^2\), then what's the necessary and sufficient condition for \(n\) s.t. \(S_n\) contains an element that is not in \(S_{n-1},...,S_1\)?

이전에 적어둔 풀이를 복붙해서 이상한 부분이 있을 수 있다.

 

n이 무승수가 아니라면, 자명히 아니다.

n이 무승수라면 가능함을 보일 것이다.

\(1\le k<n\)인 모든 무승수 k에 대해서, -k가 \(p_k\)의 이차비잉여고 -n이 \(p_k\)의 이차잉여이도록 하는 \(p_k\)를 항상 잡을 수 있는데, 이는 이차 상호 법칙을 잘 따져보고, 디리클레등차수열정리를 쓰면 된다.

이제 모든 \(p_i\)들을 전부 곱한 것을 p라고 두자. 당연히 \(1\le k<n\)인 모든 k에 대해서 \(x^2+ky^2\)은 절대로 \(v_p(x)=1\)인 x를 만들 수 없다. 한편, 구성에 의해서 어떤 p의 배수가 아닌 x,y가 존재해서 \(x^2+ny^2=0 mod p\)이도록 할 수 있다. 이제 x+ip를 적당한 i를 대입하면, \(x^2+ny^2\)은 p의 배수이며 \(p^2\)의 배수는 아니도록 할 수 있다.

앞으로도 최대한 배운 것들을 일지에 기록해두는 방향성으로 글을 올리게 될 것 같다. 그 외에도 최근에 양자역학에 관해 공부하고 있는데, 관련한 포스팅을 조만간 올리게 될 가능성도 존재한다. 최근에 의욕이 많이 없었는데, 이렇게 일지를 작성하는 것이 의욕을 고취하기를 바랄 뿐이다.