PS#3 피사노 주기

pengooseDev·2023년 6월 6일

웰-노운 피사노 주기

JS로 안풀려서 C++로 피보나치 수3를 열심히 깎아도 AC가 안뜬다.

문제의 코드

#include<stdio.h>
int main()
{
  long long n, f = 0, s = 1, mod = 1000000, i = 2;
  scanf("%lld", &n);
  while (i <= n)
  {
    long long temp = s;
    s = (f + s) % mod;
    f = temp;
    i++;
  }
  long long answer;
  printf("%d", n == 0 ? f : s);
  return 0;
}

"피사노 주기"를 공부해야 풀 수 있는 문제란다.

그게 뭔데 씹덕아

피보나치 수열 F1, F2, F3, ... Fi가 존재할 때, n으로 나눈 값에 주기가 존재한다.

알고리즘

const getPisano = (n) => {
	let prev = 0, curr = 1, res = 0;
  	
  	for (let i 0; i < n * n; i++) {
        let temp = prev;
        prev = curr;
        curr = (temp + curr) % n;
      
        if (prev === 0 && curr === 1) {
            res = i + 1;
            break;
        }
    }
  
  
  return res;
}

문제 적용

바로 문제를 풀어보자

> #9471 피사노주기(S4)

피사노 주기를 구하는 함수를 작성하여 입력받은 값에 대하여 출력만 하면 되는 간단한 문제이다.

const [_, ...input] = require("fs")
.readFileSync("/dev/stdin")
.toString()
.trim()
.split('\n');

const getPisano = (n) => {
	let prev = 0, curr = 1, res = 0;
	
  	for (let i = 0; i < n * n; i++) {
    	let temp = prev;
        prev = curr;
        curr = (temp + curr) % n;
     
        if (prev === 0 && curr === 1) {
            res = i + 1;
            break;
        }
    }

  return res;
}

let answer = '';
for (let i of input) {
    const [num, m] = i.split(' ').map(Number);
    answer += `${num} ${getPisano(m)}\n`    
}

console.log(answer);

> #9471 피보나치 수 3(S4)

피사노 주기 사용해서 풀어보자.

/* get pasino period */
const mod = 1000000;

const getPisano = (n) => {
	let prev = 0, curr = 1, res = 0;
  	
  	for (let i = 0; i < n * n; i++) {
        let temp = prev;
        prev = curr;
        curr = (temp + curr) % n;
      
        if (prev === 0 && curr === 1) {
            res = i + 1;
            break;
        }
    }
  
  return res;
}

const pisano = getPisano(mod);

/* create fibo dp */
const input = BigInt(require("fs").readFileSync("/dev/stdin").toString().trim()) % BigInt(pisano);

let n = Number(input % BigInt(pisano));
const fibo = new Array(n + 1).fill(0);
fibo[0] = 0;
fibo[1] = 1;

for (let i = 2; i <= n; i++) {
    fibo[i] = (fibo[i - 1] + fibo[i - 2]) % mod;
}

console.log(fibo[input] % mod);