집합 $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$를 전처리 하는 것은 필수이다...

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

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