FNUM

Xem PDF
Tất cả bài nộp
Các bài nộp tốt nhất
Xem hướng dẫn
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
    vietnammuonnam_mvn    6:26 p.m. 27 Tháng 8, 2024 ← đã chỉnh sửa

    Thu hồi

    1 phản hồi

    • -3
      BestFlo2k9    10:24 a.m. 29 Tháng 7, 2024

      include <bits/stdc++.h>

      using namespace std;
      string s;
      int tong = 0;
      int main()
      {
      cin >> s;
      s += '0';
      for (int i = 0;i < s.size();i++) tong += s[i] - '0';
      cout << tong%9;
      }
      code cho ai can

      2 phản hồi

      • 1
        tknhatbm    9:54 a.m. 1 Tháng 5, 2022

        sao làm code:

        n=int(input())
if n%9==0:
    print(9)
else:
    print(n%9)

        mà bị time limit nhỉ?

        1 phản hồi

        • 0
          new4letuantu    6:40 p.m. 2 Tháng 11, 2021

          2 bài này giống nhau nè :v
          https://lqdoj.edu.vn/problem/1920sodep


          • 10
            phamngocphuc2008    10:44 a.m. 28 Tháng 10, 2020

            Bài này em có cách giải hơi ngu, nếu thấy sai mong các anh chỉ bảo.

            Cách thứ nhất: Dùng đệ quy, cộng hết các chữ số lại, nếu tổng lớn hơn 9 thì chạy lại lần nữa

            Code:

            int findNum(string input)
{
    int answer{};
    for (int i = 0; i < input.size(); i++) answer += int(input[i]) - 48;
    return (answer <= 9) ? answer : findNum(to_string(answer));
}

int main()
{
    string input;
    cin >> input;
    cout << findNum(input);
}

            Cách thứ hai: Chỉ cần tính tổng hết cả dãy rồi sau đó lấy số dư của số đó chia cho 9, trường hợp chia hết xuất ra 9.

            Code:

            int main()
{
    string input;
    cin >> input;

    int sum {0};

    for (int i = 0; i < input.size(); i++)
    {
        sum += int(input[i]) - 48;
    }
    if (sum % 9 == 0)
        cout << '9';
    else
        cout << sum % 9;
}

            • 2
              SPyofgame    2:33 a.m. 19 Tháng 6, 2020

              Updated Editorial


              • 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;
}