oVeron

소수와 짝수 세미소수의 합으로 \(N\)을 몇 개나 나타낼 수 있는지 묻는 문제이다.먼저 에라토스테네스의 체를 이용해 \(NloglogN\)으로 소수와 짝수 세미소수를 구한다.다음으로 소수와 짝수 세미소수를 다항식으로 나타낸다. 예를 들어 소수 5를 \(1 * x^5\)로 나타내는 식이다.그 후 두 다항식을 FFT를 이용해 곱하면, 소수와 짝수 세미소수의 합의 개수가 계수에 나타난다.#include using namespace std;typedef long long ll;typedef pair pii;typedef pair pll;typedef tuple tiii;typedef complex cd;const double PI = acos(-1);const int MAXN = 1000001;int prim..

알고리즘/baekjoon 2024. 8. 11. 13:39

https://www.acmicpc.net/problem/4924 4924번: 정수론 싫어 정수론 중간고사를 마치고 집으로 돌아온 상근이는 패닉에 빠졌다. 유일하게 공부를 하지 않은 것이 오일러 피 함수(Euler's totient function, \(\varphi \))였는데, 그 함수에 관한 문제만 나왔기 때문이 www.acmicpc.net 우선 에라토스테네스의 체를 응용해 \(p(n)\)을 구한다. 에라토스테네스의 체에서는 소수의 배수를 전부 걸러냈지만, 여기서는 1부터 백만까지 소인수분해한 인수의 개수를 구해야 하기 때문에 소수의 배수를 걸러내는 대신 소수의 배수를 나누어떨어지지 않을 때까지 나눠준다. 직접 구해보면 \(p(n)\)의 최댓값은 19이므로 빠른 시간 내에 \(p(n)\)을 구할 수..

알고리즘/baekjoon 2023. 5. 30. 12:18

https://www.acmicpc.net/problem/1016 1016번: 제곱 ㄴㄴ 수 어떤 정수 X가 1보다 큰 제곱수로 나누어 떨어지지 않을 때, 그 수를 제곱ㄴㄴ수라고 한다. 제곱수는 정수의 제곱이다. min과 max가 주어지면, min보다 크거나 같고, max보다 작거나 같은 제곱ㄴㄴ수 www.acmicpc.net 관찰 \(min\)의 범위가 \(100000^{2}\)이기 때문에, \(2^{2}\)부터 \(1000000^{2}\)까지 살펴보면 된다. 그런데 어떤 수 N이 제곱수로 나누어 떨어지는 것을 알기 위해 2부터 1000000까지의 제곱수로 전부 나눠봐야 할까? 제곱수는 어떤 수 x를 제곱한 것이고 이 x는 소수로 나누어 떨어지므로, 모든 제곱수는 어떤 소수의 제곱수로 나누어 떨어진다...

알고리즘/baekjoon 2023. 5. 8. 12:23

소수 판정 소수는 1 또는 자기 자신 이외에는 나누어떨어지지 않는 수이다. 따라서 어떤 수 N이 소수인지 판단하기 위해서는 N을 2 이상 \(\left \lfloor \sqrt{N} \right \rfloor\) 이하의 수로 나누어 떨어지는지 확인하면 된다. 이때 1은 예외 처리해 주어야 한다. #include using namespace std; typedef long long ll; typedef pair pii; typedef pair pll; typedef tuple tiii; int main() { ios::sync_with_stdio(0); cin.tie(0), cout.tie(0); int N; cin >> N; bool prime{true}; if (N == 1) prime = false;..

알고리즘/algorithm 2023. 4. 25. 18:00

https://www.acmicpc.net/problem/15965 15965번: K번째 소수 자연수 K가 주어진다.(1 ≤ K ≤ 500,000) www.acmicpc.net 1. 에라토스테네스의 체의 시간복잡도는 O(nlog(logn)) 이다. 2. 50만번째 소수는 천만을 넘지 않는다. #include #include #include #include #include #include #include #include #include #include using namespace std; typedef long long ll; typedef pair pii; int K; bool prime[10000001]; int k{ 1 }; int ans{ 2 }; int main() { ios::sync_with_..

알고리즘/baekjoon 2023. 2. 13. 10:00