10166 관중석

문제를 간략히 정리하면 아래와 같습니다.

1. 반지름이 각각 d1, d1 + 1, d1 + 2, ..., d2 - 1, d2인 동심원들이 있습니다.
2. 반지름이 n이라면, 북쪽 점부터 시작해 원을 n등분합니다.
3. n등분한 위치에서 중심을 향해 선을 그었을 때, 다른 점과 만난다면 (겹친다고 표현하겠습니다) 이 점은 버립니다.

문제를 보고, 원 전체를 1로 본다면 각 점은 어떻게 될까 생각을 해 보았습니다. (원을 북쪽 점에서 중심 방향으로 잘라 펼친다고 생각해봅시다)

그럼, 반지름이 n인 원(이하 n-원)에서 시계방향으로 (혹은 반시계방향으로) i번째 위치는 i/n이라고 볼 수 있습니다. (i = 0, 1, 2, ..., n - 1) 이를 앞으로 점의 "위치 수"라고 하겠습니다. 즉, n-원의 i번째 점의 위치 수는 i/n입니다.

겹치는 점들을 보면, 서로 위치 수가 같다는 것을 알 수 있습니다. 예를 들어 2-원의 1번째 점과 6-원의 3번째 원은 위치 수가 1/2로 같습니다.

여기서 알 수 있는 또 다른 사실은, n-원의 모든 점들은 (k*n)-원에 있는 점과 겹치게 된다는 것입니다. i / n = (k * n) / (k * n) 이기 때문입니다.

따라서, (n의 약수)-원에서 각각 새로 나타난 점의 개수를 모두 n-원의 점의 개수에서 빼 주면 n-원에서 새로 추가되는 점의 개수가 나오게 됩니다. n-원의 점의 개수는 n개이므로, 각 원의 개수 초기값을 n으로 두고 1부터 n까지 반복문을 돌며 각 원의 배수 원에서 자기 점의 개수를 빼 주면 됩니다.

for (int n = 1; n <= d2; ++n) {
    auto spots = sieve[n];
    for (int multiple = n * 2; multiple <= d2; multiple += n) {
        sieve[multiple] -= spots;
    }
}

다만, d1에서부터 원을 세기 때문에, d1보다 작은 원에서 추가된 점들이 이후에 나타나지 않는 문제가 발생합니다. 때문에, 점의 개수를 빼 주는 과정에서 처음으로 반지름이 d1 이상인 배수 원이 나타나면 따로 값을 더해주는 방식을 취했습니다.

int first_appear = 1;
for (int n = 1; n <= d2; ++n) {
    auto spots = sieve[n];
    bool first_added = n >= d1;
    for (int multiple = n * 2; multiple <= d2; multiple += n) {
        if (!first_added && multiple >= d1) {
            first_appear += spots;
            first_added = true;
        }
        sieve[multiple] -= spots;
    }
}

이후, 지금까지 구한 점의 개수를 더해주면 됩니다.

auto sum = first_appear + accumulate(sieve + d1 - 1, sieve + d2, 0);

위 과정을 여기서 테스트해보실 수 있습니다.

참고: 실제 코드는 본문의 코드와 다른 점이 있습니다. 계산량을 줄이거나(n = 2부터 시작) 속도를 조금이라도 빠르게 하기 위해(시프트 연산을 이용한 곱셈, 나눗셈) 약간의 변형이 포함되어 있으니 그 점에 주의하여 주시기 바랍니다.