JArchive 프로그래밍 일기

int pow(int a, int b){
 if(b == 0) return 1; 
 if(b == 1) return a;
 if(b%2 == 0) { // 짝수 승이라면, 
  int temp = pow(a, b/2);
  return temp*temp;
 }
 return pow(a, b-1); // 홀수 승이면 1승 차이.
}

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

ll a, b, c;

ll rec(ll a, ll b){
  if(b == 0) return 1;
  if(b == 1) return a % c;

  long long temp = rec(a, b/2);
  if(b%2 == 0){ // b가 짝수라면,
    return (temp * temp) % c; // b/2승을 제곱하면 된다.
  }
  else{// b가 홀수라면, 1번 더 a를 곱해준다.
    return ((temp * temp) % c) * a % c;
  }
}

int main(void){
  ios::sync_with_stdio(0);
  cin.tie(0);

  cin >> a >> b >> c;
  cout << rec(a, b);
  return 0;
}

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

string a, b, answer;
vector<int> a_vec, b_vec;
int carry, temp_sum; // 올림수, 한 자리수 더함.

// 숫자 + '0' == 문자 
// 문자 - '0' == 숫자
int main(void){
  ios::sync_with_stdio(0);
  cin.tie(0);

  cin >> a >> b;

  if(a.size() < b.size()) swap(a, b);
  int diff_len = a.size() - b.size();

  // a, b 문자열의 문자를 하나씩 int 벡터로 넣는다.
  for(int i = 0; i < a.size() ; i++) a_vec.push_back(a[i]-'0');
  for(int i = 0; i < diff_len; i++) b_vec.push_back(0);
  for(int i = 0; i < b.size(); i++) b_vec.push_back(b[i]-'0');

  for(int i = a_vec.size()-1; i >= 0 ; i--){ // 뒤 부터 앞으로
    temp_sum = a_vec[i] + b_vec[i];

    if(carry == 1){ // 이전에 올림수가 있었다면, 1 더한다.
      temp_sum++;
      carry = 0;
    }
    if(temp_sum > 9){ 
      temp_sum %= 10;
      carry = 1; // 올림수 발생했으니까 1로 변경.
    }
    answer += (temp_sum + '0'); // 숫자를 문자열에 이어붙인다 
  }
  if(carry == 1) answer += '1'; // 올림수가 있다면, 1을 덧붙임
  reverse(answer.begin(), answer.end()); // 문자를 뒤집기 
  cout << answer;
  return 0;
}

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

int n, sum;
string a, b, tmp, fibo[10002];
vector<int> ans, num1, num2;

string big_num_sum(string s1, string s2){

  string s = "";

  // 더 긴 수를 s1에 저장한다.
  if(s1.size() < s2.size()) swap(s1, s2);

  // num1, num2 배열을 만든다.
  num1.push_back(0);
  num2.push_back(0);

  // s1이 더 긴 수니까. 그대로 num1 벡터를 채운다.
  for(int i = 0; i < s1.size(); i++)
    num1.push_back(s1[i] - '0');

  // s2가 비교적 짧은 수니까. s1, s2 길이 차이만큼 0을 num2 벡터에 채운다.
  for(int i = 0; i < s1.size() - s2.size(); i++)
    num2.push_back(0);

  for(int i = 0; i < s2.size(); i++)
    num2.push_back(s2[i] - '0');

  // num1, num2 벡터 맨 뒤부터 앞쪽으로 덧셈을 하면서 ans 벡터에 저장
  for(int i = s1.size(); i > 0; i--){
    sum = num1[i] + num2[i];
    if(sum > 9){
      num1[i-1] += 1; // 올림 수 발생했으니까 1을 더해준다.
      sum -= 10;
    }
    ans.push_back(sum);
  }

  // 맨 앞자리수에 올림수가 넘어왔다면,
  if(num1.front() != 0) s.push_back('1');

  // ans 벡터 원소 순서를 거꾸로.
  reverse(ans.begin(), ans.end());
  // ans 벡터의 숫자를 순차 출력하여 문자열 s에 이어붙인다. 
  for(auto n : ans){
    s.push_back(n+48); // 문자로 저장해야 하니까 48을 더해준다.  
  }
  num1.clear(); num2.clear(); ans.clear();
  return s;
}

int main(void) {
  ios::sync_with_stdio(0);
  cin.tie(0);

  cin >> n;

  fibo[0] = "0";
  fibo[1] = "1";

  for(int i = 2; i <= n; i++){
    fibo[i] = big_num_sum(fibo[i-1], fibo[i-2]);
  }
  cout << fibo[n];

  return 0;
}

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

int input;
string a, b, answer; // 긴 숫자를 문자로 표현
vector<int> va, vb; // 연산을 위한 벡터

string fibo(string &a, string &b){
  string res = "";

  int diff_len = b.size()-a.size(); // 숫자 길이의 차이

  for(int i = 0; i < diff_len; i++) va.push_back(0);
  for(auto str : a) va.push_back(str - '0');
  for(auto str : b) vb.push_back(str - '0');

  int carry = 0;
  for(int i = vb.size()-1; i >= 0; i--){
    int temp_sum = va[i] + vb[i];

    if(carry == 1) { // 올림수가 있었다면, 더해주고. 다시 0 으로 돌려놓음
      temp_sum++;
      carry = 0;
    }
    if(temp_sum > 9){
      temp_sum %= 10;
      carry = 1;
    }
    res += (temp_sum + '0');
  }

  if(carry == 1) res += '1';
  reverse(res.begin(), res.end());
  va.clear(); vb.clear();

  return res;
}
// 숫자 + '0' == 문자
// 문자 - '0' == 숫자
int main(void){
  ios::sync_with_stdio(0);
  cin.tie(0);

  cin >> input;

  a = "0", b ="1";

  if(input == 0) cout << 0;
  else if(input == 1) cout << 1;
  else{
    for(int i = 2; i <= input; i++){
      answer = fibo(a, b);
      a = b;
      b = answer;
    }
    cout << b;
  }
  return 0;
}

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

long long D[22];
int n;

long long fibo(int num){
  if (num == 0) return 0;
  if (num == 1) return 1;
  return fibo(num-1) + fibo(num-2);
}

int main(void) {
  ios::sync_with_stdio(0);
  cin.tie(0);

  cin >> n;
  cout << fibo(n);
  return 0;
}

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

long long D[22];
int n;

int main(void) {
  ios::sync_with_stdio(0);
  cin.tie(0);

  cin >> n;

  D[1] = D[2] = 1;
  for(int i = 3; i <= n; i++){
    D[i] = D[i-1] + D[i-2];
  }

  cout << D[n];
  return 0;
}

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

long long n, cnt;
vector<int> v;

void pisano(int m){
  v.push_back(0); // 0번째 피보나치 수
  v.push_back(1); // 1번째 피보나치 수
  v.push_back(1); // 2번째 피보나치 수

  cnt = 2; // 3번째 피보나치 수를 구하기 위해 2번째와 1을 연산해야 한다.

  while(1){
    v.push_back((v[cnt] + v[cnt-1]) % m);
    cnt++;
    if(v[cnt] == 0 && v[cnt-1] == 1) break; // 주기를 구한 순간.
  }

}

int main(void) {
  ios::sync_with_stdio(0);
  cin.tie(0);

  cin >> n;

  pisano(1000000);
  cout << v[n % cnt];

  return 0;
}

주기를 이루는 숫자를 저장하는 벡터 v를 둔다고 생각해보자 (mod으로 나눈 나머지를 저장한다)

나누는 숫자 mod은 2 이상의 숫자가 주어진다

mod가 2일 때, 피보나치 수1을 2로 나누면 나머지가 1이다.  v[0] = 0, v[1] = 1, v[2] = 1 가 된다.