유사 칸토어 비트열

n 번째 일 때 1의 개수는 4**n 개이니까 주어진 구간을 5의 배수로 나누었을 때 나눠지면 그때의 제곱수가 n 번째 단계의 1의 개수 값과 동일하다.

이런 식으로 나머지가 없어질 때까지 반복하면 주어진 값까지의 1의 개수를 구할 수 있고 a~b 구간의 값을 구하려면 b까지의 1의 개수에서 a까지의 1의 개수를 빼면 된다.

def solution(n, l, r):
    answer = 0
    l-=1
    a=b=0

    def f(x):
        for i in range(20,-1,-1):
            if 5**i<=x:
                break
        t=x//(5**i)
        if t==2:
            x=0
        if t>2:
            t-=1
        return (4**i)*t, x%(5**i) 
    
    while l or r:
        a1,l = f(l)
        b1,r = f(r)
        a += a1
        b += b1
    return b-a

def solution(n, l, r):
  answer = r-l+1
    for num in range(l-1,r):
        while num>=1:
            a,b=divmod(num,5)
            if b==2 or a==2:
                answer-=1
                break
            num=a
    return answer