![]()
https://www.acmicpc.net/problem/23820 mex(S)는 S에 포함되지 않은 가장 작은 음이 아닌 정수이다.이 때 mex({ai * aj})를 구하는 문제이다. ai의 범위는 200만 이하의 음이 아닌 정수이고, 곱으로 집합의 원소를 결정하므로 절대로 나올 수 없는 가장 작은 소수는 계산해보니 2000003이다.그러므로 어떤 수를 곱하던지 상관 없이 2000003을 넘어간다면 즉시 종료하면 되고,모든 가능한 곱을 다 계산한 이후 0 ~ 2000003까지 나오지 않은 정수를 파악하면 된다. 12345678910111213141516171819202122232425262728293031#include iostream>#include vector>#include algorithm..
https://www.acmicpc.net/problem/10244 10244번: 최대공약수들 n개의 수로 이루어진 수열 A가 주어질 때, 1≤lo≤hi≤n의 정의역을 가지는 함수 f(lo,hi)는 Alo부터 Ahi까지 모든 원소들의 최대공약수로 정의된다. lo와 hi는 수열의 원소가 아닌 인덱스라는 점에 주 www.acmicpc.net 구간 l ~ r 까지의 원소들의 최대공약수를 구했을 경우, 나올 수 있는 정수의 개수를 구하는 문제이다. 우선 주어지는 원소는 100 이하의 자연수이므로, 최대공약수의 개수도 최대 100개임을 알 수 있다. 하지만 i ~ n까지의 부분 집합을 하나하나 계산하기에는 시간적인 문제가 있으므로 이를 완전 탐색으로 접근하기에는 무리가 있어 보였다. 그래서 생각한 것은 1 ~ 1..
https://www.acmicpc.net/problem/19576 19576번: 약수 가능 한 방법 중 하나로, a2를 12로, a3을 3으로 바꾸면 된다. www.acmicpc.net 임의의 수 x, y를 잡았을 때, x%y == 0 이거나 y % x == 0이 되도록 수열 내의 원소를 바꾸어야하는데, 바꾸는 횟수가 최소가 되어야한다. 처음 접근했던 방식은 N의 범위가 1 ~ 5000이므로 반복문을 돌려 약수의 개수가 가장 많은 원소를 찾고, 해당 원소와 나누어지지 않는 원소를 바꾸는 방식이다. 그런데 코드를 돌려보니, 5 5 7 7 35 와 같은 원소가 주어졌을 때 제대로 출력이 되지 않는다는 것을 확인했고, 그래서 똑같이 반복문을 돌리되, 이번엔 약수의 개수가 아니라 나누어떨어지는 수의 개수를 구..
https://www.acmicpc.net/problem/2737 2737번: 연속 합 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 정수 하나로 이루어져 있다. 이 정수는 문제에서 설명한 N이며, 231보다 작다. www.acmicpc.net 연속되는 자연수의 합으로 해당 정수를 표현할 수 있는지 묻는 문제 당연히 임의의 자연수를 i라고 하면, 연속하는 자연수이므로 i + 1, i + 2, ... 와 같이 연속된 자연수의 합으로 정수 N을 표현해야 한다. 먼저 자연수 2 개로 N을 표현할 수 있는지 생각해보면, 연속이 시작되는 자연수 (가장 작은 자연수)를 i라고 가정하고, i + (i + 1) == N이 되어야 하므로 ( N - 1 ) % 2i == 0 이 되어야 한다. 또한, ..
https://www.acmicpc.net/problem/27725 27725번: 지수를 더하자 서로 다른 $N$개의 소수로 이루어진 집합 $P=\{p_{1}, p_{2}, \cdots, p_{N}\}$이 있다. 양의 정수 $i$에 대하여 $\frac{i}{p_{1}^{a_{1}}\times p_{2}^{a_{2}}\times \cdots \times p_{N}^{a_{N}}}$의 값이 양의 정수가 되도록 하는 www.acmicpc.net 문제가 너무 어렵게 생겨서 지레 겁을 먹었던 문제 그런데 읽다보니 그냥 소인수분해를 이용한 문제 풀이라는 것을 알고 나름 간단하게 해결했다. 다만 문제 조건 K > n; ll k, y, ans=0; for(int i=0; i> x; v.push_back(x); } ci..
