카드 나머지

시간 제한1초메모리 제한1024 MB

요약

L부터 R까지의 연속된 정수를 차례로 이어 붙인 수를 9로 나눈 나머지를 구합니다.

난이도: 보통10점 중 4점
유형: 수학, 구현
정답자: 아직 제출이 없습니다

문제

모든 정수 쌍 $a$ , $m$ (단, $m>0$ )에 대해 $a=m⋅q+r$ 이고 $0≤r\<m$ 을 만족하는 정수 $q$ , $r$ 이 유일하게 존재한다. 이것만으로는 단순하지만, 이 이론으로 더 흥미로운 일을 할 수 있는지 궁금해졌다.

지금 당신은 번호가 $L$ 부터 $R$ 까지 연속으로 적힌 카드를 들고 있다. 카드를 나란히 놓고 숫자를 순서대로 이어 붙여 하나의 큰 수를 만든다. 이 수를 $9$ 로 나눴을 때의 나머지를 구하고 싶다. 예를 들어 $L=9$ , $R=11$ 이면 카드는 9, 10, 11이고, 이어 붙이면 91011이 된다. 91011을 9로 나눈 나머지는 3이다.

입력

한 줄에 두 정수 $L$ ( $1≤L≤10^{12}$ )과 $R$ ( $L≤R≤10^{12}$ )이 주어진다. 번호가 $L$ 부터 $R$ 까지인 카드(양 끝 포함)를 들고 있다는 뜻이다.

출력

이어 붙인 수를 $9$ 로 나눈 나머지를 한 줄에 출력한다.

예제5

예제 1
입력
```
2 5
```
예상 출력
```
5
```
예제 2
입력
```
3 10
```
예상 출력
```
7
```
예제 3
입력
```
3 100
```
예상 출력
```
7
```
예제 4
입력
```
1000000000 1000000007
```
예상 출력
```
0
```
예제 5
입력
```
9 11
```
예상 출력
```
3
```