엘릭시르제

문제 링크: https://www.acmicpc.net/problem/32454 문제 풀이피사노 주기, 오일러 피 함수, 분할 정복을 이용한 거듭제곱 일단 $7^{7^{7^n}}$을 먼저 보면 벌써부터 답이 없어지는데, 이 수는 매우 크기 때문에 사실상 직접 구하는 것은 불가능하다. 그래서 접근하기가 힘든데, $7^{7^{7^n}}$번째 피보나치 수를 $10$번째 자리까지 출력하라고 적혀있다. 이 말은 피보나치 수를 구했을 때 $10^{10}$으로 나눈 값만 구하면 된다. 그렇다면 여기서 떠올리는 게 있다면 쭉쭉 풀려질 것이다. 피사노 주기를 이용하면 된다. 피보나치 수에서 나누는 값이 $10^{m} (m > 2)$라면 주기는 $15 \times 10^{m-1}$다. $m = 10$이므로 주기는 $15 ..

문제 링크: https://www.acmicpc.net/problem/32242문제 풀이폴라드 로, 정수론 처음에는 서브테스크로 나눠서 생각을 해봤는데, $A$가 0이냐 0이 아니냐를 기준으로 나눠서 생각했다. 생각해야할 케이스가 매우 많으므로 천천히 생각해봐야 한다. 1. $A=0$인 경우1-1. $B \neq 0$, $C \neq 0$ 인 경우$Bx+Cy+D=0$의 형태가 되는데 베주 항등식이 떠오를 것이다. 정수 해가 무한히 존재하는 지 혹은 없는지에 대해 알 수 있다.$GCD(B, C) = X$라 하고, 베주 항등식에 따르면 $X$가 $D$의 배수이면 정수인 $x, y$가 무수히 많기 때문에, 이를 판별해서 구하면 된다. 1-2. $B = 0$, $C \neq 0$ 인 경우$Cy+D=0$이 되고,..

A. Card Game Contest (백준 14551)조합론 각각의 덱은 독립적이므로 총 방법의 수는 $A_1$부터 $A_N$까지 곱하면 된다. 단, 덱이 없을 수도 있는데, 이때는 스킵하거나 0을 1로 바꾸면 된다. $M$으로 나눈 나머지를 구해야 하므로 곱할 때마다 모듈러 연산을 취해주면 된다.  B. 행사장 대여 (Small) (백준 14732)구현 범위가 작으므로 좌표를 받을 때마다 그 부분의 영역들을 2차원 배열에 1로 채워주면 된다. 이후 넓이를 구할 때 1의 개수를 세어주면 된다. C. 체크포인트 달리기 (백준 29891)그리디, 정렬 일단 들어오는 모든 수가 양수 혹은 음수일 때를 생각해보면, $N$이 $K$의 배수라면 거리가 먼 순서부터 체크하던지, 가까운 순서부터  체크하던지 상관없지..

문제 링크: https://www.acmicpc.net/problem/9011 9011번: 순서 n개의 정수로 된 순서 S= (s1, s2, ..., sn)가 있다. 여기서 si ≠ sj이고, 1 ≤ si ≤ n이다. S로부터 새로운 순서 R = (r1, r2, ..., rn)을 얻을 수 있는데, 여기서 ri는 S의 부분 순서 {s1, s2, ..., si-2, si-1} 중에서 www.acmicpc.net 문제 풀이 구현 R 수열의 뒷부분부터 처리하면 어렵지 않다. 처리는 R[i]+1을 중심으로 하면 된다. 가령 R수열의 마지막은 오른쪽 부분이 없고 왼쪽에는 자신보다 작은 수의 개수이므로 R[i]+1로 자명하다. 그렇다면 중복 혹은 자신보다 작은 수가 오른쪽에 있는 경우는 어떻게 해야할까? 예제 1을 ..