0과 1의 쉼터

풀이 분할 정복을 이용한 거듭제곱 알고리즘으로 행렬의 제곱을 구현해주어야 시간 초과가 발생하지 않는다. 소스코드 #include int N; void square(int result[][5], int matrix[][5]){ int temp[5][5] = {0,}; for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) for (int k = 0; k < N; k++) temp[i][j] += (result[i][k]*matrix[k][j]) %1000; for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) result[i][j] = temp[i][j] %1000; } int main(){ long long B; ..

풀이 지문이 어마무시하게 길면서 Fermat’s little theorem에 대해 설명이 친절한 문제이다. 요점은 다음과 같다. M개의 N과 S에 대해 S*N^(MOD-2)의 합들을 MOD로 나눈 나머지를 구하면 된다. 단, N^(MOD-2)를 구하는 과정에서 수가 너무 커지므로 중간과정마다 MOD로 나누어줘야 한다. 소스코드 #include const int MOD = 1e9+7; int main(){ long long sum = 0, N; int M, S; scanf("%d", &M); while (M--){ scanf("%d %d", &N, &S); long long temp = 1, k = MOD-2; while (k){ if (k & 1) temp = temp*N %MOD; k >>= 1; N ..

풀이 위의 예제는 다음과 같은 규칙이 있다. gcd(1, 소수) = 1 이므로 계산할 필요가 없으며, gcd(소수, 소수) = 소수 이다. gcd(N, M) = K일 때, gcd(N + K*i, M + K*i)는 모두 K이다. (단, i = 2~N or M) 위의 조건에서 얻은 K는 K의 제곱수가 존재할 경우 변경된다. N과 M크기를 이용해 K의 개수를 구할 수 있다. 두번째 조건에서 얻은 K들의 곱들과 세번째 조건에서 얻은 수의 중복을 피해야 한다. 다음과 같이 p+K*i (단, i = 0 ~ (p+K*i

풀이 Pisano Period를 이용해 풀이했다. 위의 내용 처럼 피보나치 수를 특정 수(n)으로 나눌 때 나머지들은 일정 주기마다 반복되는 것을 알 수 있다. 이러한 주기를 Pisano Period라고 부른다. Pisano Period는 다음과 같이 이용된다. n번째 피보나치 수를 MOD로 나눈 나머지는, N % (Pisano Period) 번째 피보나치 수를 MOD로 나눈 나머지와 같다. Pisano Period번 째의 피보나치 수가 필요하며, 이번 문제에 필요한 Pisano Period를 구하는 방법은 다음과 같다. MOD가 10의 6승이므로 Pisano Period는 1500000 = 15 * 10 ^(5) 이다. 소스코드 #include #define MOD 1000000 #define P 15..

풀이 정답은 2의 K제곱들의 합이다. "백준 13731, A" 문제에서 2의 제곱을 구하는 방식을 이용해 풀이했다. 2의 K제곱(D)들의 합(sum_D)을 차수와 계수의 곱에 곱해주는 것을 반복하면 된다. 소스코드 #include #define MOD 1000000007 int main() { int N; scanf("%d", &N); long long result = 0, C, K; for (int i = 0; i < N; i++) { scanf("%d %d", &C, &K); long long DC = (C*K)%MOD, sum_D = 1, D = 2; K--; while (K) { if (K & 1) sum_D = sum_D*D %MOD; D = D*D %MOD; K /= 2; } result = ..

풀이 비트 연산자를 사용해 풀이할 수 있다. X의 이진수를 right shift 해주면서, A를 한 번씩 제곱해주다가, X의 이진수의 가장 끝(맨 오른쪽) 숫자가 1일 때, result에 곱해주는 방식으로 풀이했다. A = 2, X = 6일 때 A X X & 1 result 2 110 false 1 4 11 true 4 16 1 true 64 0 소스코드 #include #define MOD 1000000007 int main() { unsigned long long A, X, result = 1; scanf("%llu %llu", &A, &X); A %= MOD; while (X > 0){ if (X & 1) result = (result*A) % MOD; X >>= 1; A = (A*A) % MOD;..

풀이 분할 정복을 이용한 거듭제곱 알고리즘의 기초적인 방법으로 풀이했다. 입력된 수는 int형으로 충분히 담아낼 수 있지만, 두 수의 곱은 이를 벗어나기 때문에, long long형으로 담아주어야 한다. Test Case에 주어지는 C의 값은 결과를 int형으로 출력할 수 있게 주어지는 듯 했다. 착한 문제지 쉬운 문제는 아니다. 홀수의 경우에는 A를 한번 더 곱해서 맞춰주어야 하므로 (B%2 ? A : 1) 으로 해결했다. 소스코드 #include long long mul(int A, int B, int C) { if (B > 1) { long long temp = mul(A, B/2, C); return ((temp*temp)%C * (B%2 ? A : 1)) % C; } else return A; ..