집합 $s$는 크기가 $n$이고 어떤 자연수 $m$의 약수를 모두 포함하고 있다. 그 집합의 원소들에 대해 다음 행렬을 만들었을 때 행렬식을 구하는 문제이다. \[D_{n}=\begin{vmatrix} \gcd(x_{1},x_{1}) & \gcd(x_{1},x_{2}) & ... & \gcd(x_{1},x_{n})\\ \gcd(x_{2},x_{1}) & \gcd(x_{2},x_{2}) & ... & \gcd(x_{2},x_{n})\\ ... & ... & ... & ...\\ \gcd(x_{n},x_{1}) & \gcd(x_{n},x_{2}) & ... & \gcd(x_{n},x_{n})\\ \end{vmatrix}\] 행렬식을 계산할 때 가장 단순하게 생각할 수 있는 것은 대각 행렬의 꼴을 만든 뒤에 ..

일반 물리가 재미없어서 수업시간에 푼 문제;; 아~ 시험공부 하기 싫다~~ 문제 해법으로 바로 넘어가자. $g, h$가 주어졌을 때 $gk=h^{n}+\alpha$($\alphak: k*=h if p: k*=h a=(2*k)//a-1 a*=g if a==g: g=0 return (h*a+g,a) t=int(input()) for i in range(t): g,h=map(int,input().split()) ans1=f(g,h,0) ans2=f(g,h,1) no1=0 no2=0 if ans1[0]>10**18: no1+=1 if ans2[0]>10**18: no2+=1 if gcd(ans1[0],ans1[1])!=g or r(ans1[0],ans1[1])!=h: no1+=1 if gcd(ans2[0],an..

이 문제는 $x^{n}-1$을 소인수분해 하는 것이 목적이다. 문제 지문에 나와있다시피 $x^{n}-1$은 다음과 같이 소인수분해 된다. \[x^{n}-1=\prod_{d|n} \Phi_{d}\] 양 변에 log를 취하자. \[\log(x^{n}-1)=\sum_{d|n} \log(\Phi_{d})\] 뫼비우스 역공식을 이용하면 \[\log(\Phi_{n})=\sum_{d|n} \log(x^{d}-1) \mu(n/d)\] \[\Phi_{n}=\prod_{d|n} (x^{d}-1)^{\mu(n/d)}\] 위 식을 이용해 $x^{n}-1$을 구성하는 각각의 $\Phi$들을 구하면 답을 구할 수 있다. $\mu(n/d)$의 값이 1 또는 -1인 것만 계산하면 된다. 물론 $\mu$를 전처리 하는 것은 필수이다...

처음 참가해본 대회인데 3문제나 풀어서 기쁘다. 문제들을 보자마자 느낀 것은 정말 새롭고 신기하다는 것 ㅋㅋㅋㅋㅋ 1번 문제는 그냥 Text로 복사 붙여넣기 하면 끝난다. 2번은 애초에 아는 언어가 C++20 밖에 없어서 부분 점수만 받고 끝났다. 3, 4번은 무서워서 안했다 ㅋㅋㅋ 5번을 풀 때 txt파일에 있는 단어 중에서 5개의 글자가 서로 다른 것들을 추리고 제출하고, 채점 결과를 초대로 추리고 돌리고... 하면 쉽게 풀린다. 6번이 가장 힘들었던 문제... 4시 정도에 했는데 8분 정도 노가다를 했다. 😫😫 7번도 패스 8번은 직접 육군훈련소에 가서 찾아봤는데 비밀번호가 걸려서 읽을 수가 없었다. 그래서 그냥 막 찍다가 '하이'로 부분 점수를 얻었다. 9번은 9-1번 문제에서 포기했다. 아무리 ..

이 문제는 [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)$의 차..