Optimization is Freaky Fun

• 문제 구성이 마음에 들지 않는다.. 여러개의 서브태스크가 있는데 필요로 하는 풀이방법이 다르다. 즉, 입력값을 보고, 그것으로부터 이게 어떤 서브태스크인지를 파악해서, 그 서브태스크에서 주어진 다른 조건을 함께 가정해서 문제를 풀어야 한다. 이럴거면 차라리 여러개의 문제로 나눠서 출제하는 것이 낫지 않나.
• 기본적인 풀이 방식은 [N/1]+[N/2]+...+[N/N] 을 계산 을 활용하는 것이다.
• 시작과 끝이 1부터 N이 아니라 S부터 E까지일 경우에는, 그냥 루프의 시작조건과 종료조건만 살짝 바꾸고, 마지막 부분에 처리만 추가해주면 쉽게 계산이 가능하다. 시간복잡도는 쿼리당 O(sqrt(N))이고, Q개의 쿼리를 처리해야 하니까 O(Q*sqrt(N))이 된다.
• 1번과 3번 태스크에 대해서는 이것이 가장 효율적인 방법이다. 이 방법으로 PyPy로 돌리면 4번 태스크만 시간초과가 생긴다.
• 2번,4번 태스크처럼 같은 N에 대해서 반복적인 쿼리를 필요로 할때는, prefix sum을 써서 최적화시킬수가 있다. 위의 풀이 방법은 [N/i]값을 기준으로 O(sqrt(N))개의 그룹으로 묶어서 합을 계산하는 것을 기본으로 한다. 이때 [N/i]값이 바뀔때마다 1부터 i까지의 합을 미리 저장해서 prefix sum을 만들어 놓자. 그러면 1부터 E까지에 대한 합을 계산할때, prefix sum에 저장되어 있는 수 중에서 E이하의 최대값 x를 이진검색해서 찾고 같이 저장해놓은 1~x까지의 합을 가져온다. 거기에 x부터 E까지의 합만 계산해서 더해주면 답을 구할 수 있다. prefix sum의 크기는 O(sqrt(N))이고 이것을 만드는 데 걸리는 시간도 O(sqrt(N))이다. 각 쿼리를 처리하는 것은 prefix sum을 이진검색하는 O(log(sqrt(N)) = O(logN)외에는 모두 상수시간에 계산된다. 따라서 총 시간 복잡도는 O(sqrt(N) + QlogN)이 된다.
• 이제 N이 모두 동일하면 아래의 O(sqrt(N) + QlogN) 방법을, N값이 다르면 위의 O(Q*sqrt(N)) 방법을 적용하면 된다. N이 모두 동일한지를 보려면 쿼리를 미리 모두 읽어서 확인해야 하지만, 문제 조건에 따라서, Q>10이고 N>10^6인 경우는 태스크 2번,4번에서만 가능하므로 모든 N이 동일하다는 것을 보장받을수 있다. (N이 모두 동일하면서, N이나 Q값이 저것보다 더 작을수도 있지만, 그 경우는 그냥 일반적인 방법으로 풀어도 시간내에 풀리니 상관없다.)
• 5번 태스크의 경우도 좀 더 최적화할 수 있다. [N/1]+[N/2]+…+[N/N]는 τ(1)+τ(2)+…τ(N)과 동일하다. 그리고 모든 i에 대해서 τ(i)를 구하는 것은 f(1), f(2), ... ,f(N)을 모두 계산에서 설명한대로 O(N)에 가능하다. τ(i)의 prefix sum을 만들어 놓으면, X까지의 합이 N=X일때의 결과값이 된다. 따라서 O(N+Q)에 처리 가능.
  • 하지만, 입력이 5번 태스크인지 확인하기 위해서는 진짜로 쿼리를 모두 읽어서 처리해야 하는 귀찮음이 있다. python으로는 어차피 3번 태스크에서 시간 초과가 나기 때문에 5번 태스크를 최적화해도 만점을 받는것이 불가능하고, PyPy는 5번 태스크를 최적화 안해도 통과가 되기때문에, 이부분은 구현 안하고 넘어가기로 했다. (언어별 추가시간이 주어지지 않는다)
• 실수하기 쉬운 점은, 입력이 S<E≤N 을 만족한다는 보장이 없다. 이 조건이 충족되지 않을때는 주어진 c코드가 어떤 값을 줄지 따라가서 그에 맞게 출력해줘야 한다.

"""Solution code for "BOJ 17417. Optimization is Freaky Fun".

- Problem link: https://www.acmicpc.net/problem/17417
- Solution link: http://www.teferi.net/ps/problems/boj/17417

This code should be submitted with PyPy3. Python3 gets TLE.
"""

import bisect
import sys


N_THRESHOLD = 10**5
Q_THRESHOLD = 10
INF = float('INF')


def calc_with_prefix_sum(n, s, e, prefix_sum):
    if not prefix_sum:
        psum = 0
        i = 1
        while i <= n:
            j = n // (n // i)
            psum += n // i * (j - i + 1)
            prefix_sum.append((j, psum))
            i = j + 1

    i, psum = prefix_sum[bisect.bisect(prefix_sum, (e, INF)) - 1]
    sum_to_e = psum + (e - i) * (n // e)
    if s == 1:
        return sum_to_e
    else:
        s -= 1
        i, psum = prefix_sum[bisect.bisect(prefix_sum, (s, INF)) - 1]
        sum_to_s = psum + (s - i) * (n // s)
        return sum_to_e - sum_to_s


def main():
    Q = int(sys.stdin.readline())
    prefix_sum = []
    for _ in range(Q):
        N, S, E = [int(x) for x in sys.stdin.readline().split()]
        if E < S or N < S:
            print(0)
            continue
        if Q > Q_THRESHOLD and N > N_THRESHOLD:
            # For this case, all queries should have same N value.
            print(calc_with_prefix_sum(N, S, E, prefix_sum))
            continue
        i = S
        answer = 0
        while i <= N:
            j = N // (N // i)
            if j >= E:
                answer += N // i * (E - i + 1)
                break
            answer += N // i * (j - i + 1)
            i = j + 1
        print(answer)


if __name__ == '__main__':
    main()