2986 파스칼

파스칼 코드로 되어있는 프로그램의 결과를 출력하는 문제이다.
파스칼 코드의 의미는 N-1부터 1까지 반복하면서, N과 나누어떨어지는 수가 발견되면 그 숫자가 나올때까지의 반복횟수를 출력하는것이다.

사실 이 소스를 그대로 C로 구현해도 정답이 맞아야 하지만, 얄밉게도 TLE가 발생하는 구조로 되어있다.

따라서 이 문제는 N보다 작으면서 N과 나누어떨어지는 수의 최댓값을 찾아야 하는데,
이는 N을 N의 가장 작은 약수로 나눈값과 같다.

따라서 N의 가장 작은 약수를 찾으면 되는데, 이것은 O(root(N))의 시간복잡도를 가지게 찾을 수 있다.

소스