codeforce/#641 (Div.2) (1) 썸네일형 리스트형 Codeforces Round #641 (Div.2) A. Orac and Factors f(n)은 n을 나누는 가장 작은 소수를 출력한다. 에라스토테네스의 체를 사용하여, 10^6 까지의 n에 대하여 f(n)을 구한다. 코드에서는 minDiv배열에 해당값을 저장하였다. n = f(n) + n 을 k번 반복한다. test case의 수가 100개 k가 10^9 개 이므로 k번 반복해서는 time out이 발생한다. 두번째 계산부터 f(n)은 무조건 2인데, 이는 f(n) + n의 값이 무조건 짝수이기 때문이다. f(n)이 홀수 일경우 n도 홀수이고, f(n)이 짝수인경우는 n또한 짝수이다. 이를 통해 답을 계산하면, ans = f(n) + n + (k-1) * 2 가 된다. #include using namespace std; int minDiv[1000010]; int main(){ int.. 이전 1 다음