본문 바로가기

수학205

[백준 11414] LCM [C] 풀이 gcd(x, y) = gcd(x-y, y)임을 이용해 풀이했다. A < B일때, gcd(A+N, B+N) = gcd(A+N, B-A)이므로, B-A의 약수를 이용해야 한다. 1~ B-A범위를 모두 탐색하면 시간초과가 발생하므로 다른 방법을 생각해야된다. 위의 예시에서 알 수 있듯이, 시작값(X)을 기준으로 X+N이 B-A로 나누어 떨어질 때 X~(X+B-A)구간에서 가장 작은 LCM값을 가진다는 점을 알 수 있다. X+N이 B-A로 나누어 떨어진다는 것은, B-A의 약수로도 나누어 떨어지는 것을 의미한다. 따라서, A가 B-A의 약수로 나누어 떨어지지 않을 때, N번째 수를 생성 후 LCM을 계산해 가장 작은 N값을 구하면 된다. 소스코드 #include #define ll long long int.. 2021. 8. 31.
[백준 11690] LCM(1, 2, ..., n) [C] 풀이 N이하 소수들의 가장 큰 거듭제곱들을 곱하고, 2^32로 나눈 나머지를 출력해주면 된다. 소스코드 #include #include #define MAX 100000001 bool cNum[MAX]; int main(){ for (int i = 2; i*i < MAX; i++) if (!cNum[i]) for (int j = 2*i; j < MAX; j += i) cNum[j] = true; int n; scanf("%d", &n); long long result = 1; for (int i = 2; i < MAX; i++) if (!cNum[i]){ long long temp = 1; while (temp*i 2021. 8. 30.
[백준 2904] 수학은 너무 쉬워 [C] 풀이 난이도에 비해 생각할 내용이 좀 많은 문제였다. 점수를 계산할 수들을 소수로 나누고 곱하는 과정을 통해 가장 큰 점수를 알아내는 문제이다. 즉, 입력받는 수들을 소인수분해하고, 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값이다. 문제에서 .. 2021. 8. 30.
[백준 19577] 수학은 재밌어 [C] 풀이 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 2021. 8. 30.
[백준 5615] 아파트 임대 [C] 동규부동산에서 아파트를 임대하고 있다. 아파트의 방은 아래 그림과 같이 면적이 2xy + x + y이다. (x와 y는 양의 정수)동규부동산의 카탈로그에는 아파트의 면적이 오름차순으로 적혀져 있지만, 이 중 일부는 있을 수 없는 크기의 아파트이다. 만약, 이런 크기의 아파트를 임대하겠다고 말하면, 동규는 꽝! 이라고 외치면서, 수수료만 떼어간다.동규부동산의 카탈로그에 적힌 아파트의 면적이 주어졌을 때, 있을 수 없는 크기의 아파트의 수를 구하는 프로그램을 작성하시오.입력첫째 줄에 아파트의 면적의 수 N이 주어진다. 다음 줄부터 N개 줄에 카탈로그에 적혀있는 순서대로 면적이 주어진다. N은 100,000이하이고 면적은 2^31-1이하인 양의 정수이다.출력첫째 줄에 있을 수 없는 아파트 면적의 수를 출력한다... 2021. 8. 29.
[백준 11402] 이항 계수 4 [C] 풀이 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.. 2021. 8. 28.

티스토리툴바