0과 1의 쉼터

풀이 16까지 1의 분포는 다음과 같다. N N의 2진수 1의 개수 1 1 1 2 1 0 2 3 1 1 4 4 1 0 0 5 5 1 0 1 7 6 1 1 0 9 7 1 1 1 12 8 1 0 0 0 13 9 1 0 0 1 15 10 1 0 1 0 17 11 1 0 1 1 20 12 1 1 0 0 22 13 1 1 0 1 25 14 1 1 1 0 28 15 1 1 1 1 32 16 1 0 0 0 0 33 2^x 자리 수는 2^(x+1)마다 반복된다는 것을 알 수 있다. 때문에, (N+1)을 2^(x+1)로 나눈 몫을 2^x만큼 곱하면 완전히 반복되는 구간에 존재하는 1의 개수를 구할 수 있다. 완전히 반복되지 않은 구간에서의 1의 개수는, 2^x 자리 수가 1인경우 (N+1)을 2^x로 나눈 나머지의 개수..

풀이 "백준 7677, Fibonacci"처럼, t개만큼 n번째 피보나치 수를 구하면 된다. 소스코드 #include #define ll long long const int MOD = 1e9; ll X[2][2] = {0, 1, 1, 1}; void fibo(ll result[][2], ll f[][2]){ ll temp[2][2] = {0,}; for (int i = 0; i < 2; i++) for (int j = 0; j < 2; j++) for (int k = 0; k < 2; k++) temp[i][j] += (result[i][k]*f[k][j]) %MOD; for (int i = 0; i < 2; i++) for (int j = 0; j < 2; j++) result[i][j] = temp[..

풀이 짝수번째 피보나치 수에는 다음과 같은 규칙이 있다. "백준 11444, 피보나치 수 6" 코드를 사용해 풀이했다. 소스코드 #include #define ll long long const int MOD = 1e9 + 7; ll X[2][2] = {0, 1, 1, 1}; void fibo(ll result[][2], ll f[][2]){ int temp[2][2] = {0,}; for (int i = 0; i < 2; i++) for (int j = 0; j < 2; j++) for (int k = 0; k < 2; k++) temp[i][j] += (result[i][k]*f[k][j]) %MOD; for (int i = 0; i < 2; i++) for (int j = 0; j < 2; j++) ..

풀이 홀수번째 피보나치 수에는 다음과 같은 규칙이 있다. "백준 11444, 피보나치 수 6" 코드를 사용해 풀이했다. 소스코드 #include #define ll long long const int MOD = 1e9 + 7; ll X[2][2] = {0, 1, 1, 1}; void fibo(ll result[][2], ll f[][2]){ int temp[2][2] = {0,}; for (int i = 0; i < 2; i++) for (int j = 0; j < 2; j++) for (int k = 0; k < 2; k++) temp[i][j] += (result[i][k]*f[k][j]) %MOD; for (int i = 0; i < 2; i++) for (int j = 0; j < 2; j++) ..

풀이 n, m번째 피보나치 수의 최대공약수는, gcd(n, m)번째 피보나치 수와 같다. 구글에 영어로 검색하니 바로뜬다... 이 무슨 "백준 11444, 피보나치 수 6" 코드를 사용해 풀이했다. 소스코드 #include #define ll long long const int MOD = 1e9+7; ll X[2][2] = {0, 1, 1, 1}; ll gcd(ll a, ll b){ return b ? gcd(b, a%b) : a; } void fibo(ll result[][2], ll f[][2]){ int temp[2][2] = {0,}; for (int i = 0; i < 2; i++) for (int j = 0; j < 2; j++) for (int k = 0; k < 2; k++) temp[i]..

풀이 제한시간이 12초이기 때문에 모든 쌍을 확인하면 시간초과가 발생한다. 때문에, A~B, C~D의 합을 저장하고, Binary Search을 사용해 풀이했다. 합이 0인 쌍의 개수를 모두 구해야 하므로, 다음과 같이 upper/lower bound를 구현했다. qsort(AB, N, sizeof(int), compare); qsort(CD, N, sizeof(int), compare); long long cnt = 0; for (int i = 0; i 0) right = mid; else left = mid ..

풀이 Pisano Period를 이용해 풀이했다. 위의 내용 처럼 피보나치 수를 특정 수(n)으로 나눌 때 나머지들은 일정 주기마다 반복되는 것을 알 수 있다. 이러한 주기를 Pisano Period라고 부른다. Pisano Period는 다음과 같이 이용된다. n번째 피보나치 수를 MOD로 나눈 나머지는, N % (Pisano Period) 번째 피보나치 수를 MOD로 나눈 나머지와 같다. Pisano Period번 째의 피보나치 수가 필요하며, 이번 문제에 필요한 Pisano Period를 구하는 방법은 다음과 같다. MOD가 10의 6승이므로 Pisano Period는 1500000 = 15 * 10 ^(5) 이다. 소스코드 #include #define MOD 1000000 #define P 15..