0과 1의 쉼터

풀이 짝수번째 피보나치 수에는 다음과 같은 규칙이 있다. "백준 11444, 피보나치 수 6" 코드를 사용해 풀이했다. 소스코드 #include #define ll long long const int MOD = 1e9 + 7; ll X[2][2] = {0, 1, 1, 1}; void fibo(ll result[][2], ll f[][2]){ int temp[2][2] = {0,}; for (int i = 0; i < 2; i++) for (int j = 0; j < 2; j++) for (int k = 0; k < 2; k++) temp[i][j] += (result[i][k]*f[k][j]) %MOD; for (int i = 0; i < 2; i++) for (int j = 0; j < 2; j++) ..

풀이 홀수번째 피보나치 수에는 다음과 같은 규칙이 있다. "백준 11444, 피보나치 수 6" 코드를 사용해 풀이했다. 소스코드 #include #define ll long long const int MOD = 1e9 + 7; ll X[2][2] = {0, 1, 1, 1}; void fibo(ll result[][2], ll f[][2]){ int temp[2][2] = {0,}; for (int i = 0; i < 2; i++) for (int j = 0; j < 2; j++) for (int k = 0; k < 2; k++) temp[i][j] += (result[i][k]*f[k][j]) %MOD; for (int i = 0; i < 2; i++) for (int j = 0; j < 2; j++) ..

풀이 n, m번째 피보나치 수의 최대공약수는, gcd(n, m)번째 피보나치 수와 같다. 구글에 영어로 검색하니 바로뜬다... 이 무슨 "백준 11444, 피보나치 수 6" 코드를 사용해 풀이했다. 소스코드 #include #define ll long long const int MOD = 1e9+7; ll X[2][2] = {0, 1, 1, 1}; ll gcd(ll a, ll b){ return b ? gcd(b, a%b) : a; } void fibo(ll result[][2], ll f[][2]){ int temp[2][2] = {0,}; for (int i = 0; i < 2; i++) for (int j = 0; j < 2; j++) for (int k = 0; k < 2; k++) temp[i]..

풀이 피보나치 수열에는 다음과 같은 공식이 있다. "백준 11444, 피보나치 수 6" 코드를 사용해 a+2-1번째 피보나치 수와 1을 뺀 값에, b+2번째 피보나치 수와 1을 뺀 값을 MOD로 나눈 나머지를 출력해주면 된다. 연산에 사용되는 temp, X를 초기화 해주어야 하며, 나머지간의 연산이기 때문에 음수가 나올 수 있다는 점을 유의하자. 소스코드 #include #define ll long long const int MOD = 1e9; ll X[2][2] = {0, 1, 1, 1}; void fibo(ll result[][2], ll f[][2]){ int temp[2][2] = {0,}; for (int i = 0; i < 2; i++) for (int j = 0; j < 2; j++) for..

풀이 다음과 같이 행렬을 이용해 피보나치 수를 구할 수 있다. "백준 10830, 행렬 제곱" 코드를 이용해 완성했다. 소스코드 #include #define ll long long const int MOD = 1e9 + 7; ll X[2][2] = {0, 1, 1, 1}; void fibo(ll result[][2], ll f[][2]){ int temp[2][2] = {0,}; for (int i = 0; i < 2; i++) for (int j = 0; j < 2; j++) for (int k = 0; k < 2; k++) temp[i][j] += (result[i][k]*f[k][j]) %MOD; for (int i = 0; i < 2; i++) for (int j = 0; j < 2; j++) ..

풀이 분할 정복을 이용한 거듭제곱 알고리즘으로 행렬의 제곱을 구현해주어야 시간 초과가 발생하지 않는다. 소스코드 #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 ..

풀이 오일러의 정리를 이용해서 풀이하는 문제다. 이나... 자료가 너무 부족하다. 오일러의 정리에 대해 자료를 찾던 도중 다음과 같은 자료를 찾았다. a와 n이 서로소이면, a^m ≡ 1 mod n에서 m = EPF(n)을 만족하는 정수 m이 적어도 하나 존재한다. a (mod n)에 대한 차수가 위 식의 m이 될 수 있다. (N ^ f( N, EPF(M) ) ) % M을 재귀호출해 찍었다. 풀이했다. 입력받거나 전달받은 N과 M 둘 중 하나가 1일 때, 1을 반환해주면 위 식의 계산에 따라 원하는 결과를 얻을 수 있다. 단, 제곱을 구하는 과정에서 long long으로도 담을 수 없는 수가 나온다. (N^(N^N)) mod M != (N^((N^N) mod M)) mod M 이므로, M이 아닌 EPF(..

소스코드 #include #include #define MAX 1001 bool not_prime[MAX]; int main(){ int N, K; scanf("%d %d", &N, &K); for (int i = 2; i

풀이 연속된 소수의 합이므로, 소수로만 이루어진 배열에서 투 포인트를 적용하면 된다. 에라토스테네스의 체로 소수가 아닌 것들을 구분하여 소수로만 이루어진 배열을 만들고, 투 포인트 방식으로 풀이했다. 소스코드 #include #include #include #define MAX 4000001 bool not_prime[MAX]; int sum_prime[MAX/10]; int main(){ int N; scanf("%d", &N); int sq = sqrt(N); for (int i = 2; i