[c++] 백준 11778 - 피보나치 수와 최대공약수

0. [c++] 백준  -

https://www.acmicpc.net/problem/11778

1. 풀이

1) 찾아야 하는 순서의 피보나치 수를 기본적인 피보나치 수열 구현의 방법으로 찾아낸 후, 그 두 수를 gcd()를 취해 최대공약수를 찾는 방법을 만들어 보았다.

하지만, 입력이 매우 크기에 시간초과가 발생하였다.

2) 그래서 무언가 간단하게 표현되는 방법이 존재하진 않을까 하는 생각에 수열을 적은 후, 다양하게 숫자 비교를 해보고 있었는데, 신기한 규칙이 눈에 들어왔다.

i>0일때, a[i+6] = a[i+3]*4 + a[i] 라는 규칙이 성립하고 있었다.

이제 이것을 활용해보자. 음... no answer

3) 혼자서는 답이 없어서 다른 블로그를 참고하였다 ㅠㅠ.

의외로 놀랐던건 gcd를 한 값으로 피보나치를 구했어도 상관이 없었던 것이었다.

왜이런지 더 찾아봐야지

이에 대한 오일러 파이함수라는 공식이 존재하였다.

우선, 이에 대한 설명 동영상이다. https://www.youtube.com/watch?v=VAtVfz42BxI

이야, 고등학교 논술문제 공부하는 느낌이 드는 문제였다.

2. 소스코드

1)

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33

#include<iostream>   long long cache[3]; long long ret[2]; int INF = 1000000007;   long long gcd(long long a, long long b) {     return a % b ? gcd(b, a%b) : b; }   void fibonacci(long long n, long long m) {     cache[0] = 0;     cache[1] = 1;     for (int i = 0; i < m; i++) {         if (i == n) {             ret[0] = cache[0];         }         cache[2] = cache[1]%INF;         cache[1] = (cache[0]%INF + cache[1]%INF) % INF;         cache[0] = cache[2] % INF;     }     ret[1] = cache[0]; }   int main() {     long long n, m;     std::cin >> n >> m;     fibonacci(n, m);     std::cout << gcd(ret[0],ret[1]) << "\n";         return 0; } Colored by Color Scripter

cs

3) 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66

#include<iostream> #include<vector> #include<cmath>   using namespace std;   typedef unsigned long long ull; typedef vector<vector<ull>> matrix;       const ull MOD = 1000000007;   //2*2 행렬 곱셈 matrix operator*(matrix &a, matrix &b) {     ull x = a[0][0] * b[0][0] + a[0][1] * b[1][0];     ull y = a[0][0] * b[0][1] + a[0][1] * b[1][1];     ull z = a[1][0] * b[0][0] + a[1][1] * b[1][0];     ull w = a[1][0] * b[0][1] + a[1][1] * b[1][1];       x %= MOD;     y %= MOD;     z %= MOD;     w %= MOD;       matrix ret = { { x,y },{ z,w } };     return ret; }   ull gcd(ull a, ull b) {     return a % b ? gcd(b, a%b) : b; }   //행렬 제곱 void power(matrix &F, ull n) {     if (n <= 1) return;       matrix E = { { 1, 1 },{ 1, 0 } };     power(F, n / 2);     F = F * F;     if (n % 2 != 0) {         F = F * E;     } }   //행렬을 이용한 피보나치 수열 구하기 ull fib(ull n) {     matrix F = { { 1, 1 },{ 1, 0 } };     if (n == 0)         return 0;     power(F, n - 1);     return F[0][0]; }   int main() {     ull n, m;     std::cin >> n >> m;     ull ngcd = gcd(n, m);     std::cout << fib(ngcd) << "\n";         return 0; } Colored by Color Scripter

cs

3. 참고

https://debuglog.tistory.com/156

증명

https://www.cut-the-knot.org/arithmetic/algebra/FibonacciGCD.shtml

https://ko.wikipedia.org/wiki/%EC%98%A4%EC%9D%BC%EB%9F%AC_%ED%94%BC_%ED%95%A8%EC%88%98

https://blog.encrypted.gg/140

질문이나 지적 있으시면 댓글로 남겨주세요~

도움 되셨으면 하트 꾹!