문제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 저번 문제의 경..
