글 읽기 - fibo(gcd(N, M)) != gcd(fibo(N), fibo(M)) ?

dmswl022329 2년 전 0

sol(N) 함수는 N 번째 피보나치 수열을 행렬제곱을 통해 구하는 함수입니다.

sol(N) 함수를 두번 호출하면 오류가 생기는 건가요?

sol을 한번만 호출하면 맞고 두번 호출하면 틀리네요...

어떤게 문젠지 알려주실수 있나요?

#include<bits/stdc++.h>
using namespace std;

long long N, M;
long long arr[2][2] ={
	{1, 0},
	{0, 1}
};
long long res[2][2];
long long memo[65][2][2];
long long pow2[65];

void pow_2(){
	pow2[0] = 1;
	for(int i = 1; i < 65; i++){
		pow2[i] = pow2[i - 1] * 2;
	}
}

void mul(){
	for(int n = 1; n < 65; n++){
		for(int i = 0; i < 2; i++){
			for(int j = 0; j < 2; j++){
				long long tem = 0;
				for(int k = 0; k < 2; k++){
					tem = (tem + memo[n-1][i][k]*memo[n-1][k][j]) % 1000000007;
				}
				memo[n][i][j] = tem % 1000000007;
			}
		}
	}
}

int sol(long long N_power){
	vector<int> v;
	arr[0][0] = 1;
	arr[0][1] = 0;
	arr[1][0] = 0;
	arr[1][1] = 1;
	for(int i = 62; i >= 0; i--){
		if(N_power >= pow2[i]) {
			v.push_back(i);
			N_power -= pow2[i];
		}
	}
	
	// for(int n = 0; n < v.size(); n++){
	// 	cout << v[n] << " ";
	// }
	// cout << "\n";
	for(int n = 0; n < v.size(); n++){
		for(int i = 0; i < 2; i++){
			for(int j = 0; j < 2; j++){
				long long tem = 0;
				for(int k = 0; k < 2; k++){
					tem = (tem + arr[i][k]*memo[v[n]][k][j]) % 1000000007;
				}
				res[i][j] = tem % 1000000007;
			}
		}
		for(int i = 0; i < 2; i++){
			for(int j = 0; j < 2; j++){
				arr[i][j] = res[i][j];
			}
		}
	}
	return (int)(arr[1][0] % 1000000007);
}

long long gcd(long long a, long long b){
	if(a < b) return gcd(b, a);
	long long mod = a % b;
	while(mod > 0){
		a = b;
		b = mod;
		mod = a % b;
	}
	return b;
}

int main() {
	ios_base :: sync_with_stdio(false),cin.tie(NULL),cout.tie(NULL);
	cin >> N >> M;
	memo[0][0][0] = 1;
	memo[0][0][1] = 1;
	memo[0][1][0] = 1;
	memo[0][1][1] = 0;
	pow_2();
	mul();
	cout << sol(gcd(N, M)) % 1000000007;            // 정답 출력
	cout << gcd(sol(N), sol(M)) % 1000000007;       // 오답 출력
	return 0;
}

wider93 2년 전 1

gcd(F_n, F_m)=F_gcd(n,m)은 맞는데

gcd(F_n mod p, F_m mod p) = F_gcd(n,m) mod p는 성립하지 않습니다.

dmswl022329 2년 전 0

그럼 이문제는

gcd 구한뒤 피보나치 수 구하는걸 요구하고 있는건가요?

사실상 mod 연산없이 F_n, F_m 을 구하고 gcd 를 구할 수 없을거같은데말이에요

wider93 2년 전 0

네. f_n mod p를 가지고 얻을 수 있는 것이 없으니까요.

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

문제

문제

출처

ICPC

fibo(gcd(N, M)) != gcd(fibo(N), fibo(M)) ?

dmswl022329 2년 전 0

wider93 2년 전 1

dmswl022329 2년 전 0

wider93 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말