Yule lads라는 산타클로스(?)가 왜서 불을 끄고 키고 한다는 문제이다. 총 $N$개의 집이 있고 모두 불이 켜져있다. 크리스마스의 $n$째날 전에는 $n$의 배수 번째 집의 불이 꺼지고 마지막에 숫자 1을 제외하고 모든 집에 불이 꺼질 경우 몇 명의 Yule Lads가 올 수 있을까?를 묻고 있다. 이런 경우에는 소수를 먼저 보자. 소수 번째 집에는 반드시 YL(Yule Lad)이 와야한다. 그럼 서로 다른 소수의 곱 번째 집($pq$)에는 $p$가 한 번 왔다가고 $q$가 한번 왔다 가므로 $pq$는 반드시 들러야한다. 일반화해보면 $n$의 약수의 개수가 짝수 개이면 된다는 것이다. 그런데 소수의 제곱수들을 생각해보자. 이들은 약수가 홀수 개이므로 YL이 오지 않는다. 서로 다른 $n$개의 소수..

이 문제 역시 교육적인 문제. 부분 조건을 이용해 전체 조건을 만족시키게 하는 문제이다. 문제에서 주목할 부분은 $F_{n} \bmod{10^{13}} =N$이 되는 $n$이 있냐는 것이다. 다른 말로 하면 $F_{n}\bmod{10}=N\bmod{10}$이고 $F_{n}\bmod{100}=N\bmod{100}$이고 ...를 만족하는 $n$이 있냐는 것이다. 우린 modulo가 $10^{3}$인 곳에서 시작한다. 왜냐면.. 그때부터 피보나치 수열의 피사노 주기가 $10^{n-1}*15$이기 때문이다. 알고리즘의 작동 원리는 간단하다. 법 $10^{3}$에 대해 $i$번째 피보나치 수와 $N$이 합동인 $i$들을 모아놓자. 이론적으로 1500개만 검사하면 되므로 금방 모인다. 그럼 방금 구한 각각의 인덱스..

아주 교육적인 문제 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을 곱..