유사 칸토어 비트열

https://school.programmers.co.kr/learn/courses/30/lessons/148652

프로그래머스

 

일단 5배씩 문자열이 늘어나서 20번만 한다고 해도 5**20이다 엄청 큰 수라서 저거 다 돌려서 계산하는 건 불가능하다

중요한 건 같은 패턴이 반복한다는 거다 처음 5개 그리고 다음은 25개인데 처음에 1~5 ,5~10 15~20,20~25 구간은 바로
전 단계의 전체를 반복한다 n 번째 단계를 5구간으로 나누었을 때 처음 1,2 ,4,5 구간은 n-1 번째 구간의 전체 값이다 3번째 구간은 0이라 제외하고

그러면 n 번째 일 때 1의 개수는 4**n 개이니까 주어진 구간을 5의 배수로 나누었을 때 나눠지면 그때의 제곱수가 n 번째 단계의 1의 개수 값과 동일하다 이런 식으로 나머지가 없어질 때까지 반복하면 주어진 값까지의 1의 개수를 구할 수 있고 a~b 구간의 값을 구하려면 b까지의 1의 개수에서 a까지의 1의 개수를 빼면 된다

def solution(n, l, r):
    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