2793번: 숫자의 힘
양의 정수 N이 있을 때, N을 나눌 수 없는 가장 작은 수 A를 찾을 수 있다. 예를 들어, 6은 4로 나누어 떨어지지 않으므로, A는 4가 된다. 이렇게 A를 찾은 다음, 그 수를 다시 N이라고 하고, 나눌 수
www.acmicpc.net
f(n)을 n으로 나눌 수 없는 가장 작은 수로 정의하자
이떄 strength(N) = strength(f(N)) + 1로 둘 수 있다.
f(N) = 2 인 경우는 N이 2로 나눠 떨어지지 않는 수일 때 일것이다.
f(N) = 3 인 경우는 N이 2로 나눠 떨어지지만 3으로 나눠떨어지지 않는 수 일 것이다.
f(N) = k 인 경우는 N 이 2,3,...,k-1로 나눠 떨어지지만 k로 나눠떨어지지 않는 수 일 것이다.
이때 2,3,...,k-1 로 모두 나눠 떨어진다는 의미는 2,3,...,k-1의 최소 공배수로 나눠 떨어진다는 말과 같다.
또, lcm(1,2,...,k)가 최초로 B의 최대값인 10^17-1을 초과하는 k는 42임을 프로그래밍을 통해 알 수 있다.
즉, N=2,...,41에 대해서만 나이브하게 strength(N)을 미리 구해두면 O(1)로 알 수 있게 된다.
또, f(N) = k 인 집합의 크기는 즉 lcm(2,3,...,k-1)로 나눠 떨어지지만 k로 나눠 떨어지지 않는 수의 개수는
lcm(2,3,...,k-1)로 나눠 떨어지는 수에서 lcm(2,3,...,k)로 나눠 떨어지는 수를 뺀것과 같다.
A와 B에 가장 가까운 k의 배수 경계는 ceil(A/k)*k, floor(A/k)*k 이고,
양의 정수 자료형을 가진 A에 대 간단하게 (A+k-1)/k*k, A/k*k 로도 나타낼 수 있다.
즉 우리는 [A,B]를 k의 배수 경계로 바꾸면 간단하게 구간에 속한 k의 배수의 개수를 구할 수 있다.
문제의 범위 내에서 strength의 값은 위에 언급했듯 2,3,...41중 하나이므로,
각각에 대해 개수를 구해서 합해주면 된다.