글 읽기 - 이 문제의 많은 정답자분들의 알고리즘이 궁금합니다.

temp 8년 전 0

저는 이문제를 사실 풀지 못하였습니다.

하지만 인터넷상의 다른 소스를 보며 이런방법이구나 하며 정답을 맞았습니다.

그런데 대다수의 정답자분들은 소스가 매우짧길래 참고하고있는데 모두 비슷한 알고리즘이더군요.

근데 저는 이 알고리즘이 도대체 어떻게 나온 건지, 무슨 근거로 이렇게 작성되는지 이해가 되지 않습니다.

제가 첨부한 소스는 다른 분의 소스중 일부를 가져왔습니다. 도대체 왜 m1과 m2로 잡게 되는 것이며, 그 밑의 연산과정은 어떻게 구성이 되는건가요?

혹시 이문제와 관련된 다른 알고리즘이 있나요?

scanf("%d %d", &p, &m);

int m1 = 1, m2 = 1;
int c = 0;

do{
    int temp = m1;
    m1 = m2;
    m2 = (temp + m2) % m;
    c++;
} while (m1 != 1 || m2 != 1);

printf("%d %d\n", p, c);

mendou12 8년 전 5

문제를 풀어보지는 않았는데

(a + b) mod c = (a mod c + b mod c) mod c

이걸 응용해서 한 것 같아용 헤헤

m1 ,m2는 피보나치의 n항과 n+1항을 m으로 나눈 나머지이고, 이게 피보나치의 0항과 1항을 m으로 나눈 나머지와 같아질 때까지 연산을 반복하는 거네용.

temp 8년 전 0

실례가안된다면

while (m1 != 1 || m2 != 1); 이부분 설명을 다시 해주실수있나요? 그리고 왜 이 반복문이 주기가 되는거죠?ㅜㅜ

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

문제

문제

출처

ICPC

이 문제의 많은 정답자분들의 알고리즘이 궁금합니다.

temp 8년 전 0

mendou12 8년 전 5

temp 8년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말