메뉴 건너뛰기

문제

15rm3 369게임 0  

시간메모리제출 올바른 답 비율
1초64MB
37
3
8.1%


나의 횟수나의 최근 판정시도 성공 비율
103
30.0%
369게임  

여러 사람이 둘러 앉아 즐기는 369 게임은 다음 과 같은 규칙을 가지고 있다.

규칙:

양의 정수 \(A\)에서 시작하여 차례로 사람들 이 돌아가면서 숫자를 하나씩 증가하면서 불러 나간다. 단, 부르는 숫자가 3의 배수이거나 그 숫자 에 3, 6, 9 중 하나라도 들어 있는 경우에 숫자는 부르지 않고 박수를 친다.

예를 들어, 369 게임을 17부터 시작하는 경우를 생각해보자.

박수를 X로 표현하면,

이 게임의 진행은 17-X-X-20-X-22-X-X-25–X–X-28-X-X …과 같을 것이다.

시작하는 양의 정수 \(A\)와 끝나는 양의 정수 \(B\)가 주어졌을 때, 박수를 치는 총 횟수를 구하는 프로 그램을 작성하시오.

입력

한 줄에 시 작하는 양의 정수 \(A\)와 끝나는 양의 정수 \(B\)가 순서대로 주어진다.

두 수의 범위는 \(1≤A≤B≤10^{100,000}\)이다.

출력

박수치는 총 횟수를 \(20,150,523\)으로 나눈 나머지를 출력한 다.

예시
1입력
1 12
출력
4
출처
2015년 한국 정보올림피아드 지역 본선 중등부 3번 문제
위로