:: ADVANCE ::

BAEKJOON ONLINE JUDGE 11444 피보나치 수 6 https://www.acmicpc.net/problem/11444 input이 매우 크기 때문에 그냥 구할 수 없다.피보나치 행렬과 제곱의 이진수 응용을 이용해서 구해야 한다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455#include #include using namespace std; #define Namuge 1000000007 vector multipleMatrix(vector &first, vector &second){ long long int t; long long int temp; vect..

[수학][피보나치] 피보나치 수 피보나치 수 * 피사노 주기피보나치 수를 k로 나눈 나머지는 주기를 가진다.이 때의 주기를 피사노 주기라 한다. * 피보나치 수 행렬 응용 피보나치 관련 문제피보나치 수피보나치 수 2피보나치 수 3피보나치 수 4피보나치 수 5피보나치 수 6피보나치 수의 확장피사노 주기피보나치 수의 합피보나치 수의 제곱의 합홀수번째 피보나치 수의 합짝수번째 피보나치 수의 합피보나치 수와 최대공약수

BAEKJOON ONLINE JUDGE 10830 행렬 제곱 https://www.acmicpc.net/problem/10830 행렬 곱을 반복반복을 분할 정복 또는 이진수 응용법으로 시간을 단축할 수 있다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778#include #include using namespace std; int n;long long int m;vector in; void input(){ int num; scanf("%d %lld", &n, &m); for (int i = ..

[수학][Matrix] 행렬 Matrix 1. 행렬 덧셈12345for(int i = 0; i

[수학][제곱] a^n 제곱 a의 n제곱 빠르게 구하기 1. 단순 반복문 -> 시간 복잡도 O(n)1234int ans = 1;for(int i = 1; i > n의 이진수 중 1에 해당할 때 곱하여 나간다.1234567891011int times(int a, int n){ int ans = 1; while(n > 0) { if(n % 2) ans *= a; a *= a; n /= 2; } return ans;}cs >> a는 반복문을 돌 때마다 (이진수의 자리수를 옮길 때 마다)a *= a를 통해서 제곱을 해 준다. 관련 문제https://www.acmicpc.net/problem/1629

BAEKJOON ONLINE JUDGE 2004 조합 0의 개수 https://www.acmicpc.net/problem/2004 조합 nCm의 0의 개수는n!의 0의 개수 - (m!의 0의 개수 + (n - m)!의 0의 개수)이는 (n!의 min(2개수, 5개수) - ((m!의 min(2개수, 5개수) + ((n - m)!의 min(2개수, 5개수))를 하여 구할 수 있다. n!의 2의 개수, 5의 개수 구하는 방법은 [1676 팩토리얼 0의 개수] 참고 위 참고에서 첫 번째 개수를 구하는 방법으로는 [2004 조합 0의 개수]문제를 풀 수가 없다. (문제의 입력 범위가 매우 크기 때문에 time limit가 난다. 따라서 두번째 제시한 방법으로 구하면 아무런 문제 없이 문제를 풀 수 있다. 1234..

BAEKJOON ONLINE JUDGE 1676 팩토리얼 0의 개수 https://www.acmicpc.net/problem/1676 이 문제는 팩토리얼 계산 결과값에서 0의 개수를 찾는 것이 아니다. 팩토리얼이 결국 곱으로 이루어진 연산이기 때문에 그리고 0은 10을 얼마나 곱하느냐에 따라 결정이 되기 때문에 팩토리얼을 이루는 수의 소인수 중에서 2와 5의 개수에 따라 결정이 된다. 정리를 하면 N! = 1 x 2 x 3 x ... x N ex) 10! = 3628800 10! = 1 x 2 x 3 x 4 x 5 x 6 x 7 x 8 x 9 x 10 10! = 1 x 2 x 3 x (2 x 2) x 5 x (2 x 3) x 7 x (2 x 2 x 2) x (3 x 3) x (2 x 5) 10! = 2^..

BAEKJOON ONLINE JUDGE 11635 소인수분해 https://www.acmicpc.net/problem/11653 소인수 분해라고 해서 소수 여부를 판단할 필요는 없다.2부터 하여 나누어 떨어지는 가장 작은 값이 n이 가지고 있는 소인수이다.또한, n을 소인수 분해했을 때 나타날 수 있는 인수 중 가장 큰 값은 root(n)이다.따라서, 2부터 root(n)까지 반복문을 돌면서 n을 나눌 수 있으면, 나누고, 나눌 수 없을 때까지 계속한다. 123456789101112131415161718192021222324252627#include void factorize(int n){ int i; if (n

BAEKJOON ONLINE JUDGE 6588 골드바흐의 추측 https://www.acmicpc.net/problem/6588 123456789101112131415161718192021222324252627282930313233#include int prime[1000001]; void checkprime(){ int i, j; for (i = 2; i

BAEKJOON ONLINE JUDGE 9613 GCD 합 https://www.acmicpc.net/problem/9613 각 입력의 조합을 만들어서 gcd를 구하여 합하면 되는 문제 1234567891011121314151617181920212223242526272829303132333435363738#include int gcd(int n, int m){ if (m == 0) return n; return gcd(m, n % m);} int main(){ int t; int n; int i, j; long long int sum; int num[101]; scanf("%d", &t); while (t--) { sum = 0; scanf("%d", &n); for (i = 0; i