일단 저의 빡머가리로 풀어보려니 다른 방법은 떠오르지 않았습니다.
제가 어떻게 풀었냐

r까지 1을 다 더한 값을 구함.
l-1까지 1을 다 더한 값을 구함.
둘을 빼 결과를 구함
그럼 어떻게 1을 다 더한 값을 구했을까
먼저 규칙을 잠깐 보면

n = 1 일 때 size = 5 = 5의 1승
n = 2 일 때 size = 25 = 5의 2승
n = 3 일 때 size = 125 = 5의 3승

1의 개수는 4의 n승

n = 1 , 11011
n = 2 , 11011 11011 00000 11011 11011
n = 3 , 11011 11011 00000 11011 11011 / 11011 11011 00000 11011 11011 / 00000 00000 00000 00000 00000 / ----

n = 1 11011 5개
n = 2 5개 5개 5개 5개 5개 -> 25개
n = 3 25개 25개 25개 25개 25개 -> 125개
n = 4 125개 125개 125개 125개 125개 -> 625개

n은 n-1의 전체 개수가 5개 모여 만들어진다. = 5개의 영역으로 구분이 가능하다

만약에 n = 3 , l = 28 , r = 98 일 때를 구하면
27(l-1) / 25 ( n-1의 전체 size ) = 몫 1 나머지 2
25개의 1묶음이 1개 있고 2개가 남는다는 의미.
25개일 때 1은 4의 2승만큼 있으니까 16을 더하고

나머지 3을 가지고 n을 하나 내린 상태로 다시 반복합니다.
n = 3 27/25 => 몫 1 나머지 2 -> l까지 합 += 1(몫)x16(4의 2승) = 16
n--
n = 2 3(위에서 나온 나머지)/5 => 몫 0 나머지 3 -> l까지 합 += 0(몫)x4(4의 1승) = 0
n--
n = 1 intArrayOf(1,2,2,3,4)에서 나머지 2-1 = 1 번째 index의 값 = 2 -> I까지 합 += 2
하면 l-1까지의 합은 16+0+2가 되어 18이 됩니다.

가운데 00000 묶음 부분은 어떻게 처리하냐 고민이 될 텐데
11011 11011 00000 11011 11011 은
11011 11011 11011 11011 11011 에서 11011 하나를 빼면 나오는 수입니다.
만약에 영역이
25 25 25 25 25 일 때
몫이 3 이상이면 몫이 4라 했을 때 4개의 묶음으로(16*4) 먼저 구하고 -1 묶음 (-16) 하거나 4-1 묶음으로 구해서 처리하면 되겠습니다.
이렇게 해서 마지막 n= 1이 되면 나머지에서 -1 한 값이 누적합 array = [ 1 , 1 , 2 , 3 , 4 ]의 index 가 되어 더하고 break 하면 구할 수 있습니다.
나머지가 없다면 묶음이 딱 떨어진다는 뜻이므로 첫 반복에서 값을 구하고 반복문을 종료하면 됩니다.

그래서 r까지의 합을 구하고 l-1 까지의 합을 구해서 빼면 그 사이에 l부터 r까지 1을 더한 값이 나오게 됩니다.

n=1 일 때 처리는 따로 해주시고, Long을 조심하시기 바랍니다.
저는 코틀린을 사용합니다.
pow 사용하신다면 꼭 Long으로 잘 나오는지 확인해 보시기 바랍니다.
또 저는 답 반환형에 int 쓰여있길래 그냥 아무 생각 없이 int로 처리해서 왜맞틀!!! 거리다가 이틀 뒤에 Long으로 바꾸고 통과했습니다....

부족한 글솜씨지만 조금이라도 도움이 되면 좋겠습니다.