0과 1의 쉼터

풀이 난이도에 비해 생각할 내용이 좀 많은 문제였다. 점수를 계산할 수들을 소수로 나누고 곱하는 과정을 통해 가장 큰 점수를 알아내는 문제이다. 즉, 입력받는 수들을 소인수분해하고, N개의 수들이 가장 큰 gcd값을 가지도록 소인수를 재분배하는 문제이다. 1e6까지의 78,498개의 소수들을 구하고, 입력받은 num에 대해 소인수분해를 하면서 소인수의 개수를 세주어야 한다. 다음의 예제를 보자. 8 = 2*2*2 24 = 2*2*2 *3 9 = 3*3 일때, N개의 수에 대해 2는 6개, 3은 3개가 존재한다. 이때 N = 3개의 수에 대해 각 수가 가져야할 인수들의 평균 개수는 2는 2개(6/N), 3은 1개(3/N)이므로, N개의 수들이 인수를 2*2*3으로 가질때가 가장 큰 gcd값이다. 문제에서 ..

풀이 euler_phi(x) = n/x가 성립하기 위해서는, n/x가 정수 이여야 한다. 즉, x는 n의 약수이어야 한다. n의 약수들을 모두 구한 후 오름차순으로 정렬해서 최소의 x를 찾아도 되고, 약수를 구해서 바로 계산을 해도된다. O(n^(1/2)) 만에 약수를 구하는 방법을 사용했다. 소스코드 #include #define min(a, b) a < b ? a : b int euler_phi(int n){ int euler = n; for (int p = 2; p*p

동규부동산에서 아파트를 임대하고 있다. 아파트의 방은 아래 그림과 같이 면적이 2xy + x + y이다. (x와 y는 양의 정수)동규부동산의 카탈로그에는 아파트의 면적이 오름차순으로 적혀져 있지만, 이 중 일부는 있을 수 없는 크기의 아파트이다. 만약, 이런 크기의 아파트를 임대하겠다고 말하면, 동규는 꽝! 이라고 외치면서, 수수료만 떼어간다.동규부동산의 카탈로그에 적힌 아파트의 면적이 주어졌을 때, 있을 수 없는 크기의 아파트의 수를 구하는 프로그램을 작성하시오.입력첫째 줄에 아파트의 면적의 수 N이 주어진다. 다음 줄부터 N개 줄에 카탈로그에 적혀있는 순서대로 면적이 주어진다. N은 100,000이하이고 면적은 2^31-1이하인 양의 정수이다.출력첫째 줄에 있을 수 없는 아파트 면적의 수를 출력한다...

풀이 Fermat’s little theorem을 기반으로 한 Lucas' theorem으로 풀이했다. Lucas' theorem는 다음과 같다. 쉽게, nCk를 M으로 나눈 나머지를 구하기 위해서는 N과 K를 M진 전개해 얻은 각 자릿수의 조합끼리 곱하고 M으로 나누면 된다. ex) input : 100 45 13 100 = 13*7 + 1*9 45 = 13*3 + 1*6 int result = 1; while (N || K){ result = result*nCk(N%M, K%M, M) %M; N /= M, K /= M; } nCk는 Fermat’s little theorem으로 구했다. 소스코드 #include int nCk(int N, int K, int M){ int A = 1, B = 1; fo..

풀이 "백준 11401, 이항 계수 3"보다 N의 범위가 작은 문제이다. 소스코드 #include const int MOD = 1e9+7; int main(){ long long N, K, A = 1, B = 1; scanf("%d %d", &N, &K); for (int i = N; i > N-K; i--) A = A*i %MOD; for (int i = K; i >= 2; i--) B = B*i %MOD; N = 1, K = MOD-2; while (K){ if (K & 1) N = N*B %MOD; K >>= 1; B = B*B %MOD; } printf("%d", A*N %MOD); } 출처 및 참고자료 15791번: 세진이의 미팅 모태 솔로인 세진이는 이번에는 꼭 여자친구를 사귀어야겠다는 마음으..

풀이 "백준 11401, 이항 계수 3"의 확장 문제이다. M개의 N과 K에 대해 이항 계수를 계산해야 하므로, 미리 4e6까지의 factorial과 역원을 구해주면 된다. 소스코드 #include #define ll long long #define MAX 4000001 const int MOD = 1e9+7; int A[MAX] = {1}, B[MAX]; int pow(ll a, int b){ ll result = 1; while (b){ if (b & 1) result = result*a %MOD; b >>= 1; a = a*a %MOD; } return result; } int main(){ for (ll i = 1; i < MAX; i++) A[i] = A[i-1]*i %MOD; B[MAX-1] ..

풀이 "백준 11401, 이항 계수 3"보다 N의 범위가 작은 문제이다. 소스코드 #include const int MOD = 1e9+7; int main(){ long long N, K, A = 1, B = 1; scanf("%d %d", &N, &K); for (int i = N; i > N-K; i--) A = A*i %MOD; for (int i = K; i >= 2; i--) B = B*i %MOD; N = 1, K = MOD-2; while (K){ if (K & 1) N = N*B %MOD; K >>= 1; B = B*B %MOD; } printf("%d", A*N %MOD); } 출처 및 참고자료 16134번: 조합 (Combination) \(\begin{pmatrix}N\\R\end{p..

풀이 MOD가 소수이기 때문에, A = N! - (N-K)!와 B = K!를 MOD로 나누며 구하고, Fermat’s little theorem를 이용해 ( A* B^(MOD-2) )%MOD를 구하면 된다. 소스코드 #include const int MOD = 1e9+7; int main(){ long long N, K, A = 1, B = 1; scanf("%d %d", &N, &K); for (int i = N; i > N-K; i--) A = A*i %MOD; for (int i = K; i >= 2; i--) B = B*i %MOD; N = 1, K = MOD-2; while (K){ if (K & 1) N = N*B %MOD; K >>= 1; B = B*B %MOD; } printf("%d", ..

풀이 입력받은 N개의 수들이 M으로 나누었을 때, 나머지가 모두 동일하도록 하는 M을 구하는 문제이다. 단순하게 해결하기에는 정답 비율이 처참하다, 시간 초과를 생각해 효율적으로 M을 구하는 방법을 고안했다. N개의 수들을 다음과 같이 표현할 수 있다. arr[0] = M*q_0 + r arr[1] = M*q_1 + r arr[2] = M*q_2 + r " " arr[N-1] = M*q_N-1 + r M의 범위는 다음의 조건을 따른다. N >= 2일 때, 2번째 N보다 큰 M은 존재하지 않는다. (x = arr[1] - arr[0]) = M*(q_1 - q_0)이 성립하며, x의 약수 중에 N개의 수에 대해 만족하는 M이 존재한다. x의 약수가 아니더라도 M이 될 수 있으므로, x를 포함한 x의 약수를 ..

풀이 8자리수의 소수를 확인하기 위해 1e8만큼의 공간을 할당하면 메모리 제한에 막힌다. 심지어 조건에 맞는 모든 소수의 개수가 100개도 안된다. 때문에, 다음과 같은 규칙을 찾아 문제를 해결했다. N의 자릿수는 2, 3, 5, 7 이어야 한다. 2를 제외한 모든 짝수는 소수가 아니기 때문에 홀수만 탐색해야 한다. 소스코드 #include #include int prime(int num){ int sq = sqrt(num); for (int i = 2; i