Ngày kỉ niệm sinh nhật

Xem PDF

Điểm: 200 (p) Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Nhân ngày sinh nhật của Henry \((8/9/2050)\), cậu ấy đã được một người bạn của mình đố bài toán kì diệu như sau:

  • Cho một dãy số nguyên dương được xác định như sau: \(a_0=p(p\in \mathbb{N}^{*})\)\(a_i(i\ge 1)\) bằng tổng bình phương các chữ số của \(a_{i-1}\). Và dãy này chỉ dừng lại khi có một số đã xuất hiện trước đó !

Ví dụ:

  • \(3\rightarrow 9 \rightarrow 81 \rightarrow 65 \rightarrow 61\rightarrow 37 \rightarrow 58 \rightarrow 89 \rightarrow 145 \rightarrow \text{...} \rightarrow 89\)
  • Biết rằng: Với mọi \(p\in \mathbb{N}^{*}\) thì dãy đã cho luôn có tận cùng là \(1\) hoặc \(89\). (Quả là một điều kì diệu phải không nào !!!!)

Yêu cầu:

  • Hỏi có bao nhiêu giá trị của \(p< N\) thỏa mãn dãy \(\left\{a_i\right\}\) có tận cùng là số \(89\).

Input:

  • Một dòng duy nhất chứa số nguyên dương \(N(1\le N\le 10^5)\).

Output:

  • In ra số lượng \(p\) thỏa mãn yêu cầu bài toán.

Test 1

Input
3
Output
1
Note

Từ \(1\) đến \(2\), chỉ có duy nhất số \(2\) là thỏa mãn yêu cầu bài toán. Vì \(2\rightarrow 4 \rightarrow 16 \rightarrow 37 \rightarrow 58 \rightarrow 89 \rightarrow 145 \rightarrow \text{...} \rightarrow 89\)


Bình luận

Không có bình luận nào.