FNUM

Xem PDF
Tác giả:
admin
Dạng bài
Điểm: 200 (p) Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Misaki có một số \(N\), cô ấy đố bạn tìm ra được \(FNUM\) của số đó. Một \(FNUM\) được xác định là tổng các chữ số của số đó, sau đó lại tính tổng các chữ số của số mới tạo được cho đến khi chỉ còn 1 chữ số duy nhất. Bạn hãy tìm ra số cuối cùng đó nhé!

Input

  • Dòng đầu tiên và duy nhất chứa 1 số nguyên \(N\) \((1 \leq N \leq 10^{1000000})\)

Output

  • In ra 1 số nguyên là \(FNUM\) của \(N\).

Example

Test 1

Input 
29
Output 
2
Note

Các số được tạo ra lần lượt là \(29 \rightarrow 11 \rightarrow 2\)

Bình luận


  • 3
    SPyofgame    6:21 p.m. 5 Tháng 6, 2020 ← chỉnh sửa 5

    Spoiler Alert

    Hint 1

    • Nhận xét rằng hàm \(f(x) =\) tổng các chữ số của \(x\) nó sẽ giảm rất nhanh

    Cụ thể: \(f(x) \leq 9 * \lceil\log_{10}x\rceil\)

    Sau đó ta chỉ cần tính f(f(..f(x)..)) tới khi nào 1 ≤ x ≤ 9

    Hint 2

    • Đầu tiên ta tính \(x = f(input_string)\)

    Vì \(f(max\_val) \leq 9 * \lceil\log_{10}(max\_val)\rceil \leq 9 * 1000000\)

    Nên khi ta tính trước, ta sẽ đưa số \(x\) về kiểu dữ liệu \(int\)

    Hint 3

    • Online Solving: Ta có thể không cần nhận xâu

    Reference AC code | \(O(\log_{10}n)\) time | \(O(1)\) auxiliary space | Online Solving, Math

    C++
    inline bool isDigit(char c) { return '0' <= c && c <= '9'; }
int main()
{
    int n = 0;
    for (char c; isDigit(c = getchar()); n += (c - '0'));
    while (n > 9)
    {
        int new_n = 0;
        do new_n += n % 10; while (n /= 10);
        n = new_n;
    }
    cout << n;
    return 0;
}
      • 4 bình luận nữa