글 읽기 - 피보나치 최대공약수 질문입니다

his130 6년 전 0

행렬을 이용해서 피보나치 값을 구하고,

그 값을 유클리드 호제법을 이용해서 gcd를 구하는데

틀렸습니다 가 나오는데 어디서 문제가 발생하는 걸까요?

%mod 는 제가 모든곳에 붙여버렸습니다..

#include<iostream>
#include<vector>

using namespace std;
const long long mod = 1000000007;
typedef vector<vector<long long>> matrix;
matrix operator *(matrix &A, matrix &B)
{
	matrix ret(2, vector<long long>(2));

	for (int i = 0; i < 2; i++)
	{
		for (int j = 0; j < 2; j++)
		{
			long long sum = 0;
			for (int m = 0; m < 2; m++)
			{
				sum += ((A[i][m]%mod) * (B[m][j]%mod))%mod;
			}
			ret[i][j] = sum%mod;
		}
	}

	return ret;

}
matrix calc(matrix &A, long long B)
{
	if (B == 0)
	{
		matrix ret(2, vector<long long>(2));
		ret[0][0] = 1, ret[0][1] = 0, ret[1][0] = 0, ret[1][1] = 1;
		return ret;
	}
	else if (B % 2 == 0)
	{
		matrix temp = calc(A, B / 2);
		return temp*temp;
	}
	else
	{
		matrix temp = calc(A, B - 1);
		return A*temp;
	}

}
long long gcd(long long a, long long b)
{
	if (b == 0)
	{
		return a%mod;
	}
	else
	{
		return gcd(b, a%b)%mod;
	}
}
int main()
{
	long long n, m;
	scanf("%lld %lld", &n,&m);
	matrix F(2, vector <long long>(2));
	F[0][0] = 1, F[0][1] = 1, F[1][0] = 1, F[1][1] = 0;
	
	long long a = calc(F, n)[0][1]%mod;
	long long b = calc(F, m)[0][1]%mod;

	printf("%lld\n", gcd(a, b)%mod);

	return 0;
}

jh05013 6년 전 2

(a%m, b%m)의 최대공약수와 (a, b의 최대공약수)%m은 다릅니다.

his130 6년 전 0

피보나치 성질 중 하나를 이용해야만 하겠군요..

rhs0266 6년 전 3

힌트를 드리면, 8번째 피보나치 수가 21인 것입니다.

유클리드 호제법이 gcd(a,b) = gcd(b,a-b) 이라는 사실에 집중해보세요.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

피보나치 최대공약수 질문입니다

his130 6년 전 0

jh05013 6년 전 2

his130 6년 전 0

rhs0266 6년 전 3

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말