아주 교육적인 문제 xudyh's sieve를 잘 활용할 수 있냐를 묻고 있다.(아마 그럴거다) xudyh's sieve를 유도하면서 어떻게 식을 변형할지 알아보자. 앞으로 어떤 함수의 1부터 $N$까지 부분합을 $S_{f}(N)$이라 적겠다. 위 테그닉은 $S_{f*g}(N)$과 $S_{g}(N)$을 쉽게 계산할 수 있을 때 $S_{f}(N)$을 쉽게 계산하는 방법에 대해 말해준다. 다음 식과 함께 시작하자. $$S_{f*g}(N)=\sum_{d=1}^{N} g(d)S_{f}(\lfloor \frac{N}{d} \rfloor)$$ 이때 적절한 변형을 통해 다음을 얻는다. \[S_{f}(N) = \frac{1}{g(1)}(S_{f*g}(N) - \sum_{d=2}^{N} g(d)S_{f}(\lfloor ..

이 문제는 제목이 거짓임을 1초만에 알아차릴 수 있다. 1557번의 제한이 제곱된 것인데 논리적인 흐름은 거의 비슷하다. 둘 다 이진탐색을 이용한다는 것? 이 문제가 어려운 이유는 시간제한이 말도 안되게 빡빡하기 때문... 연산 횟수를 무진장 줄이는 것이 포인트이다. 먼저 이 수가 몇 번째 square free number인지 알아보자. 다음 식을 이용한다. $$\sum_{i=1}^{\sqrt{n}} \mu(i)\lfloor \frac{n}{i^{2}} \rfloor$$ 이 식이 나온 이유는 포함 배제의 원리로 쉽게 생각할 수 있다. 1부터 천천히 생각해보자. 1인 경우 전체 $n$을 더한다. $2, 3$ 등 소수인 경우는 그 소수로 이루어진 제곱수의 개수를 빼준다. 제곱 ㅇㅇ수의 경우 개수를 아예 세지..

문제는 참 간단하다. $$\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$의..

굉장히 재미있는 문제! 이 문제에서 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을 곱..

각각의 $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

'냠냠' 이라는 문제이다! 냠냠 $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..