Infinity Triples

시간 제한4초메모리 제한2048 MB

요약

1 ≤ a < b ≤ m이고 n ≤ m인 삼중항 (n, a, b) 중에서 밑 b의 반복 숫자 a, aa, aaa... 가 무한히 많이 n으로 나누어떨어지는 것의 개수를 센다.

난이도: 어려움10점 중 8점
유형: 수학, 정수론, 조합론
정답자: 아직 제출이 없습니다

문제

Consider numbers in base $b$ where all digits are equal to $a$ with $1 \leq a < b$ . We call a triple $(n, a, b)$ an infinity triple if infinitely many of those numbers are divisible by $n$ .

For example, $(3, 9, 10)$ is an infinity triple because infinitely many of the numbers $9$ , $99$ , $999$ , $\ldots$ are divisible by $3$ . The triple $(7, 9, 10)$ is also an infinity triple, but $(5, 9, 10)$ is not.

Given $m$ , count the number of infinity triples with $1 \leq n \leq m$ and $1 \leq a < b \leq m$ .

입력

The input contains one integer $m$ ( $2 \leq m \leq 10^5$ ).

출력

Output one integer, the number of infinity triples with $1 \leq n \leq m$ and $1 \leq a < b \leq m$ .

힌트

In the first sample, $(1, 1, 2)$ is the only infinity triple.

In the second sample, the infinity triples are $(1, 1, 2), (1, 1, 3), (1, 2, 3), (2, 1, 3), (2, 2, 3),$ and $(3, 1, 2)$ .

예제3

예제 1
입력
```
2
```
예상 출력
```
1
```
예제 2
입력
```
3
```
예상 출력
```
6
```
예제 3
입력
```
42
```
예상 출력
```
25055
```