geunyang   1년 전

문제

모든 자리 숫자가   $a$  이고   $1 \leq a < b$  이면서  $n$  으로 나누어떨어지는  $b$  진수 정수   $s$  가 무수히 많을 때, 세 쌍   $(n,~a,~b)$  를 '무한대 세 쌍'이라고 한다.

예를 들어,  $(3,~9,~10)$ 의 경우  $9$ ,  $99$ ,  $999$  등 무수히 많은 수가 3으로 나누어떨어지므로 무한대 세 쌍이라 할 수 있다. 또  $(7,~9,~10)$ 도 무한 세 쌍이라 할 수 있다. 하지만  $(5,~9,~10)$ 은 무한대 세 쌍이 아니다.

 $m$ 이 주어졌을 때,  $1 \le n \le m$ 이고  $1 \le a < b \le m$ 인 무한대 세 쌍  $(a,~b,~n)$ 의 개수를 구하는 포르그램을 작성하시오.

입력

첫 번째 줄에  $2 \le m \le 10^5$ 인 정수  $m$ 이 주어진다.

출력

 $1 \le n \le m$ 이고  $1 \le a < b \le n$ 인 무한대 세 쌍  $(a,~b,~n)$ 의 개수를 출력한다.   

예제 입력 1                                                          예제 출력 1

2                                                                                                                                          1

예제 입력 2                                                          예제 출력 2

3                                                                                                                                          6

예제 입력 3                                                          예제 출력 3

42                                                                                                                                        25055

노트

첫 번째 예제에서는  $(1,~1,~2)$ 가 유일한 무한대 세 쌍이다. 두 번째 예제에서는  $(1,~1,~2)$ ,  $(1,~1,~2)$ ,  $(1,~2,~3)$ ,  $(2,~1,~3)$ ,  $(2,~2,~3)$ 과  $(3,~1,~2)$ 의 6쌍이 가능한 무한대 세 쌍이다.

출처

Camp > Petrozavodsk Programming Camp > Summer 2024 > Day 5: Der Kontest D번

댓글을 작성하려면 로그인해야 합니다.