PS(44)
-
[BOJ 16644] Easy Problem
이 문제는 제목이 거짓임을 1초만에 알아차릴 수 있다. 1557번의 제한이 제곱된 것인데 논리적인 흐름은 거의 비슷하다. 둘 다 이진탐색을 이용한다는 것? 이 문제가 어려운 이유는 시간제한이 말도 안되게 빡빡하기 때문... 연산 횟수를 무진장 줄이는 것이 포인트이다. 먼저 이 수가 몇 번째 square free number인지 알아보자. 다음 식을 이용한다. \[\sum_{i=1}^{\sqrt{n}} \mu(i)\lfloor \frac{n}{i^{2}} \rfloor\] 이 식이 나온 이유는 포함 배제의 원리로 쉽게 생각할 수 있다. 1부터 천천히 생각해보자. 1인 경우 전체 $n$을 더한다. $2, 3$ 등 소수인 경우는 그 소수로 이루어진 제곱수의 개수를 빼준다. 제곱 ㅇㅇ수의 경우 개수를 아예 세지..
2022.06.16 -
[BOJ 17372] 피보나치 수의 최대공약수의 합
문제는 참 간단하다. \[\sum_{i=1}^{n} \sum_{j=1}^{n} \gcd(F_{i},F_{j})\] 를 구하면 된다. 그런데 어떻게 빨리 구하냐가 문제인데... 이 식을 변형해보자. $\gcd(i,j)=d$라고 고정하고 각 $d$에 대해 뭘 계산해야 하는지 알아보자. 변형된 식은 다음과 같다. \[\sum_{d=1}^{n} F_{d} C(d)\] 여기서 $C(d)$는 $\gcd(i,j)=d$인 쌍의 개수를 의미한다. $F_{d}$인 이유는 $\gcd(F_{i},F_{j})=F_{\gcd(i,j)}$이기 때문! 또한 다음을 알 수 있다. \[C(d)=2\sum_{i=1}^{n/d} \phi(i) - 1\] 이는 $d=1$일 경우를 생각해보면 편하다. $d=1$일 때 $i$를 고정하고 $j$의..
2022.06.16 -
[BOJ 18151] DivModulo
굉장히 재미있는 문제! 이 문제에서 DivModulo를 정의한다. 표기는 $\mathbb{dmod}$라고 한다. 계산 방법은 다음과 같다. $d \nmid r$라 가정하면 \[r\cdot d^{h} (\mathbb{dmod}\ d) = r \pmod{d}\] 즉, $d$의 거듭제곱을 없애고 모듈러를 구하면 된다. 조합에서 $d$의 소인수들을 모두 제외시킨 뒤 $d$의 거듭제곱을 이룰 수 있는 소인수들만을 제외하고 나머지는 다시 곱해주면 문제 해결! 먼저 주어진 $D$의 소인수들을 모두 찾고 prime power로 나타내자. 앞서 서술한 Modulo Prime Power Trick의 방법을 이용하면 prime power에 대해 조합의 나머지를 구할 수 있다. 다만 값을 리턴할 때 prime power을 곱..
2022.05.16 -
[BOJ 13174] 괄호
각각의 $n$에 대하여 대칭 축을 기준으로 왼쪽에 $k$쌍의 괄호가 존재하는 경우의 수를 $h(n,k)$로 정의하자. 그럼 다음이 성립한다. \[h(n,k)=h(n-1,k-1)+h(n-1,k)\] \[h(n,k)=0\ \ k>=1){ if(k&1) s=s*n%mod; n=n*n%mod; } return s; } int main(){ ll i,n,ans=0,K,card=1,end; scanf("%lld %lld",&n,&K); end=n/2; if(n%2==0) end-=1; ans=K*fpow(K+1,2*end)%mod; for(i=1;i
2022.05.10 -
[BOJ 7938] Mniam mniam
'냠냠' 이라는 문제이다! 냠냠 $n\times m$ 격자에서 원점으로부터 각 점들로 직선을 긋는데 서로 다른 직선의 개수를 구하는 문제로 바꿔 볼 수 있다. 그럼 겹치는 직선이 뭔지만 알면 문제를 풀 수 있겠다. 기울기가 $b/a$이고 기약분수라고 한다면 $2b/2a,\ 3b/3a...$등 이 겹치는 직선이므로 1개만 세야한다. 이때 관찰할 수 있는 사실은 $b/a$가 기약분수가 아니면 반드시 겹치는 직선이 된다는 사실이다. 그럼 $b/a$가 기약분수가 되는 $a,b$쌍의 개수를 세면 된다. 이것은 다음과 같이 나타난다. \[\sum_{i=1}^{n} \sum_{j=1}^{m} [\gcd(i,j)=1]\] 이때 Mobius inversion을 적용하면 \[\sum_{d=1}^{\min(n,m)} \mu..
2022.05.10 -
[BOJ 3752] 최대공약수 행렬식
집합 $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}\] 행렬식을 계산할 때 가장 단순하게 생각할 수 있는 것은 대각 행렬의 꼴을 만든 뒤에 ..
2022.04.14