0과 1의 쉼터

풀이 "백준 7677, Fibonacci"처럼, t개만큼 n번째 피보나치 수를 구하면 된다. 소스코드 #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]){ ll 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++) result[i][j] = temp[..

풀이 n이 -1일 때까지 n번째 피보나치 수를 출력해주면 된다. "백준 11444, 피보나치 수 6" 코드를 사용해 풀이했다. 10,000으로 나눈 나머지로 계산해 출력하면 된다. 소스코드 #include #define ll long long #define MOD 10000 ll X[2][2] = {0, 1, 1, 1}; void fibo(ll result[][2], ll f[][2]){ ll 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++) fo..

풀이 T만큼 "백준 11778, 피보나치 수와 최대공약수"을 반복하는 문제이다. 소스코드 #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][j] += (result[i][k]*f[k][j]) %MOD; for (int i = 0; i < 2; i++) fo..

풀이 n번째 피보나치 수의 제곱의 합은 다음과 같은 규칙으로 구할 수 있다. "백준 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..

풀이 짝수번째 피보나치 수에는 다음과 같은 규칙이 있다. "백준 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; ..