반응형 정수론6 백준 27172번 수 나누기 게임 - C++ 풀이 1. 약수&배수 관계인 수들의 결투만 의미가 있다. 2. 어떤 수 x의 모든 약수는 1 ~ sqrt(x)까지 순회하여 찾을 수 있다. 3. 각 xi에 대해 xi의 모든 약수들과 결투한다. 1. 약수&배수 관계인 수들의 결투만 의미가 있다. 두 수가 서로 약수와 배수 관계인 경우에만 점수에 변화가 생긴다. 따라서 주어진 수들의 약수&배수 관계에만 집중하자. 2. 어떤 수 x의 모든 약수는 1 ~ sqrt(x)까지 순회하여 찾을 수 있다. 어떤 수 x의 모든 약수는 1부터 sqrt(x)까지로 모두 나누어떨어지는지 확인하는 방식으로 구할 수 있다. 만약 x가 i로 나누어 떨어진다면, i와 x/i는 x의 약수이다. 이때 i = x/i인 경우는 주의하여 처리하여야 한다. 2. 각 xi에 대해 xi의 모든 약수들과.. 2023. 7. 9. 백준 6588번 골드바흐의 추측 - C++ 풀이 1. n 이하의 모든 소수 i에 대해 (n-i)가 소수인지 판별한다. 1. n 이하의 모든 소수 i에 대해 (n-i)가 소수인지 판별한다. 에라토스테네스의 체를 이용하여 백만 이하의 모든 소수를 구한다. n이하의 모든 소수 i에 대해 n-i가 소수인지 판별하면 된다. 이때 i를 오름차순으로 순회하고, 답이 나올 경우 순회를 종료시키면 b-a가 가장 큰 답을 구할 수 있다. 백만 이하의 소수 개수는 약 8만 개이므로, 이 풀이의 시간 복잡도는 O(80,000*T)이다. 이때 T(테스트 케이스 수)가 10^5이므로 시간 초과가 날 것 같았는데 시간 초과가 나지 않았다. 이에 관련된 질문과 답을 아래 게시글에서 발견하였다. 글 읽기 - 이 문제 제한시간이 1초인데 왜 되나요? 댓글을 작성하려면 로그인해야 합니.. 2022. 9. 20. 백준 16134번 조합 - C++ 풀이 1. nCr = n! / (n-r)!r! 의 정의대로 계산한다. 2. 나눗셈은 모듈러 곱셈 역원을 이용하여 계산한다. 1. nCr = n! / (n-r)!r! 의 정의대로 계산한다. 조합 nCr의 정의대로 반복문을 통해 계산할 것이다. 2. 나눗셈은 모듈러 곱셈 역원을 이용하여 계산한다. (A*B) mod C = (A mod C) * (B mod C) mod C 임을 이용하여 곱셈을 계산하고, 나눗셈의 경우 1,000,000,007이 소수이므로 모듈러 곱셈 역원을 이용하여 계산한다. 모듈러 곱셈 역원은 분할정복을 이용한 거듭제곱을 사용해서 구하면 된다. #include using namespace std; typedef long long ll; const ll MOD = 1000000007; ll pow.. 2022. 8. 30. 백준 11778번 피보나치 수와 최대공약수 - C++ 풀이 1. gcd(f(m), f(n)) = f(gcd(m, n))이다. 2. 유클리드 호제법을 이용하여 gcd(m, n)을 구한다. 3. 분할 정복을 이용하여 gcd(m, n)번째 피보나치 수를 구한다. 1. gcd(f(m), f(n)) = f(gcd(m, n))이다. 위와 같은 피보나치의 성질을 이용해서 푸는 문제였다. 증명은 여기를 참고했다. https://math.hmc.edu/funfacts/fibonacci-gcds-please/ 2. 유클리드 호제법을 이용하여 gcd(m, n)을 구한다. 먼저 m과 n의 최대 공약수를 구해야 한다. 유클리드 호제법을 사용하여 O(logN)에 구해준다. 3. 분할 정복을 이용하여 gcd(m, n)번째 피보나치 수를 구한다. 피보나치 수열을 행렬의 거듭제곱으로 나타낸 .. 2022. 7. 22. 백준 4355번 서로소 - C++ 풀이 1. N을 소인수 분해한다. 2. 오일러 피 함수를 사용하여 서로소의 개수를 구한다. 1. N을 소인수 분해한다. 오일러 피 함수를 사용할 것이다. 이를 위해 N의 소인수를 모두 구해둔다. 2. 오일러 피 함수를 사용하여 서로소의 개수를 구한다. N과 서로소인 1부터 N까지의 정수의 개수를 구하는 함수인 오일러 피 함수를 이용하여 서로소의 개수를 구한다. #include #include using namespace std; typedef long long ll; // 소인수분해 vector calcDivisors(int N) { vector divisors; int n = N; for (int i=2; i*i 1) divisors.push_back(n); return divisors; } int coun.. 2022. 7. 18. 이전 1 2 다음 반응형
