Phép Tính Căn Số

Điểm: 7,00 (OI)

Giới hạn thời gian: 1.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Dạng bài

Ngôn ngữ cho phép

Ada, Algol, Assembly, Awk, C, C#, C++, D, Dart, Forth, Fortran, Go, Groovy, Java, Javascript, Kotlin, Lisp, Lua, Nim, ObjC, Pascal, Perl, PHP, Pike, Python, Racket, Ruby, Rust, Scheme, Scratch, Sed, TCL, Typescript, V, Zig

Với một số nguyên dương $x$ , đặt $s (x)$ là tổng các chữ số của $x$ trong hệ thập phân. Căn số $d (x)$ được định nghĩa đệ quy: nếu $s (x) \leq 9$ thì $d (x) = s (x)$ , ngược lại $d (x) = d (s (x))$ . Ví dụ $d (6543) = d (6 + 5 + 4 + 3) = d (18) = 9$ .

Cho một bài toán "với ba số nguyên dương $A, B, C$ thuộc $[1, N]$ , kiểm tra xem đẳng thức $A \cdot B = C$ có đúng không", Billy đề xuất thuật toán sau dựa trên tính chất $d (x y) = d (d (x) \cdot d (y))$ :

Nếu $d (d (A) \cdot d (B)) = d (C)$ thì Billy kết luận $A \cdot B = C$ đúng; ngược lại kết luận sai.

Hãy đếm số bộ ba $(A, B, C)$ với $A, B, C \in [1, N]$ mà thuật toán của Billy cho kết quả sai (tức là điều kiện căn số thoả mãn nhưng thực tế $A \cdot B \neq C$ ).

Dữ liệu vào

Một dòng duy nhất chứa số nguyên $N$ .

Dữ liệu ra

Một số nguyên — số bộ ba $(A, B, C)$ mà thuật toán của Billy cho kết quả sai.

Ràng buộc

$1 \leq N \leq 10^{6}$ .

Ví dụ

Input	Output	Giải thích
4	2	Hai bộ ba khiến thuật toán sai là $(3, 4, 3)$ và $(4, 3, 3)$ : $d (3 \cdot 4) = d (12) = 3 = d (3)$ nhưng $3 \cdot 4 = 12 \neq 3$ .
5	6	Sáu bộ sai gồm $(3, 4, 3), (4, 3, 3), (2, 5, 1), (5, 2, 1), (4, 5, 2), (5, 4, 2)$ .
1	0	Chỉ có bộ duy nhất $(1, 1, 1)$ và $1 \cdot 1 = 1$ nên Billy không sai.

Bình luận

Không có bình luận tại thời điểm này.