문제https://www.acmicpc.net/problem/11693시간 제한메모리 제한solved.ac 티어1초256MB골드 1풀이 역시 문제 날먹은 수학 이번 문제는 정수론 문제이다. 이 문제를 이해하기 위해서는 사전지식이 필요하다. 임의의 자연수 n에 대해 n이 다음과 같이 소인수분해된다고 해보자. 이때 n의 모든 약수의 합은 다음과 같이 나타낼 수 있다. 각 소인수에 대해 등비수열의 합을 구하고, 이 값들의 곱을 구하면 그것이 약수의 합이 된다. 해당 식을 전개하면 결국 n의 모든 약수들이 나오기 때문이다. 또한, 다음 성질이 성립한다는 것을 알 것이다. 이로 인해 n^m은 다음과 같이 나타낼 수 있다. 이제 이 모든걸 섞어보면 될 것이다. 결국 구해야하는 것은 다음 식이 된다. 각 항을 계..
문제https://www.acmicpc.net/problem/7501시간 제한메모리 제한solved.ac 티어1초128MB다이아몬드 5풀이 일단 영어 지문을 읽으면 토악질이 나오는 나지만, 그래도 해석은 가능한 수준의 영어라 읽어보았다. 이러니 저러니하지만, 정리하면 구간 [A, B]에서 다음을 만족하는 정수를 K를 구하는 문제이다.K는 홀수이다.(K-1)! ł K^2. 즉 (K-1)!은 K^2로 나누어 떨어지지 않는다.정수론에서 제일 특별한 수는 항상 소수이다. 이 문제에서도 소수와 소수가 아닌 경우를 생각해보자. K가 소수라면, (K-1)!은 절대로 K^2로 나누어 떨어지지 않는다. 증명도 간단하다. 귀류법으로 생각해서 (K-1)!이 K^2으로 나누어 떨어진다고 해보자. 이는 (K-1)!의 소인..
문제https://www.acmicpc.net/problem/4149시간 제한메모리 제한solved.ac 티어1초128MB플래티넘 1풀이 밀린 문제 정리하기. 오일러 피함수 정리하다가 갑자기 폴라드-로 알고리즘으로 넘어간 나. 그래서 이번엔 폴라드-로 알고리즘이다. 저번 문제에서 설명했지만, 폴라드-로 알고리즘을 사용하여 O(N^1/4)의 시간복잡도로 풀어낼 수 있다. 해당 문제에 적용하면 최대 2^15.5번의 탐색을 거친다 5만번도 안된다. 폴라드-로 문제에 대한 설명은 다음을 참조하자.https://codejin.tistory.com/308 코드#include #define ALL(X) X.begin(), X.end()#define endl '\n'using namespace std;using ll ..
문제https://www.acmicpc.net/problem/13926시간 제한메모리 제한solved.ac 티어2초512MB다이아몬드 5풀이 밀린 문제 정리하기. 오일러 피함수 문제이다. 그런데 밀러라빈 소수 판별법과 폴라드-로 알고리즘을 섞은... 괴랄한 알고리즘의 문제이다. 저번 GCD(n,k) = 1와 설명은 같은 문제이다. (https://codejin.tistory.com/306) 백준 11689번 C++ 풀이문제https://www.acmicpc.net/problem/11689시간 제한메모리 제한solved.ac 티어1초256MB골드 1풀이 밀린 문제 정리하기, 오일러 피함수 문제는 계속된다. 오일러 피함수에 대해 계속 정리중이기 때문에, 해당codejin.tistory.com 저번 문제의 경..
문제https://www.acmicpc.net/problem/23832시간 제한메모리 제한solved.ac 티어1초512MB골드 1풀이 밀린 문제 정리하기. 이번에도 여전히 오일러 피함수이다. 이 문제는 1~N번 정점을 그래프로 만들 것이다. 이때 정점간에 간선을 만드는 조건은 정점 a, b가 각각 서로소여야 한다. 이때 간선의 개수를 구하는 문제이다. 나는 처음에 이게 오일러 피함수 문제인지 헷갈렸다. 서로소의 개수와 연관되이었다보니 오일러 피함수가 가능할 것 같다 생객해보다가 풀이를 떠올렸다. 문제가 조금 말이 어려워서 그렇지 조금 차근차근 풀어나가보자. 간선 없이 정점만 놓고 생각해보자. 임의의 정점 a는 a보다 큰 서로소인 정수와도 연결되어야 하고, a보다 작은 서로소와도 연결되어야 한다. a보..
문제https://www.acmicpc.net/problem/11689시간 제한메모리 제한solved.ac 티어1초256MB골드 1풀이 밀린 문제 정리하기, 오일러 피함수 문제는 계속된다. 오일러 피함수에 대해 계속 정리중이기 때문에, 해당 문제는 오일러 피함수 문제임을 바로 알 수 있다. 말이 수식으로 나와서 어려울수 있지만, 자연수 n에 대해 n 이하의 자연수 k가 GCD(n, k) = 1을 만족한다는 뜻은 n과 k는 서로소라는 뜻과 동치이다. 오일러 피함수는 n 이하의 n과 서로소인 자연수의 개수를 세는 함수이기 때문에 오일러 피함수를 사용하는 문제임을 알 수 있다.코드#include using namespace std;using ul = uint64_t;ul n;void sol() { ul res..
문제https://www.acmicpc.net/problem/19577시간 제한메모리 제한solved.ac 티어1초 (추가 시간 없음)1024MB플래티넘 5풀이 밀린 문제 정리하기, 그중에서도 오일러 피함수 두번째 문제이다. 이번 문제는 대놓고 나 오일러 피함수요 하고 있다. 다만 형태가 좀 특별한데, x * phi(x) = n을 만족하는 x를 찾는 문제이다. n은 입력으로 주어진다. 우리는 이 식만으로 힌트를 얻을 수 있다. 우선, 오일러 피함수의 결과값은 무조건 자연수이다. 오일러 피함수의 정의가 phi(n) = (n 이하의 n과 서로소인 정수의 개수)이기 때문에, 무조건 자연수이다. x와 n, 그리고 phi(x)는 모두 자연수이기 때문에 phi(x) = n/x라는 식을 유도할 수 있고, n/x는 ..
문제https://www.acmicpc.net/problem/4355시간 제한메모리 제한solved.ac 티어1초128MB골드 1풀이 오랜만에 밀린 문제 정리하기이다. 아마 내가 지금 당장 정리하고 싶다는 욕망이 드는 문제가 아니고선, 풀었던 문제를 알고리즘별로 묶어서 한번에 처리하지 않을까 싶다. 지금까지도 풀었던 최단경로 문제부터 정리했었다. 이번 문제가 알고리즘별로 묶어서 정리하는 그 시초가 될 것 같다. 이번 알고리즘은 오일러 피함수, 오일러 토션트함수이다. 사실 정수론, 해석학, 대수학등, 수학 과학을 꽤 좋아하는 입장에서, 수학적인 알고리즘도 굉장히 좋아한다. 뭐... 그걸 딥하게 파고들어서 이해하는건 별개의 몫이지만 말이다. 오일러 피함수는 자연수 n에 대해 자연수 n과 서로소인 n이하의..
