Chỉ số UQ

Xem PDF

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

Cho một số \(n\). Ta định nghĩa chỉ số \(\text{UQ}\) của \(n\) được tính như sau:

  • Nếu \(n=1\) hoặc \(n\) là số nguyên tố thì \(\text{UQ}(n)=n\)
  • Nếu \(n\) là hợp số thì \(\text{UQ}(n)\) bằng tổng \(\text{UQ}\) của tất cả ước khác \(n\) của \(n\).

Yêu cầu: Cho số nguyên dương \(n\), tính \(\text{UQ}(n)\).

Input

  • Gồm nhiều dòng, mỗi dòng gồm duy nhất \(1\) số \(n\) có giá trị không quá một tỉ. Đầu vào kết thúc bởi số \(0\). Dữ liệu đảm bảo sẽ không quá \(10\) trường hợp cần kiểm tra.

Output

  • Mỗi dòng xuất ra \(\text{UQ}(n)\) tương ứng.

Example

Test 1

Input
6
20
36
0
Output
6
19
50

Bình luận


  • 8
    huyhau6a2    7:20 a.m. 12 Tháng 2, 2022

    cho một số hint đơn giản nè:

    • Các số nhỏ thường bị gọi hàm UQ rất nhiều. Làm thế nào để tính nhanh chúng?
    • Ta có thể lưu trước đáp án UQ của các số nhỏ không
    • Làm sao để số lần gọi UQ không quá nhiều

    ==>Giải: đệ quy có nhớ:

    • Ta có thể lưu kết quả những giá trị nhỏ, nếu số lớn thì khi gọi hàm UQ, nó sẽ có khả năng lướt qua các số nhỏ, ta có thể tính nhanh mà không cần gọi hàm số nhỏ đó

    VD: Ta đã biết UQ(9)=4, UQ(6)=6, UQ(4)=3
    UQ(36)
    =UQ(18)+UQ(12)+UQ(9)+UQ(6)+UQ(4)+UQ(3)+UQ(2)+UQ(1)
    = (UQ(9)+UQ(6)+UQ(3)+UQ(2)+UQ(1)) + (UQ(6)+UQ(4)+UQ(3)+UQ(2)+UQ(1)) +4+6+3+3+2+1
    =4+6+3+2+1+6+3+3+2+1+4+6+3+3+2+1
    =50

    Rõ ràng là nhanh hơn hẳn

    Bonus: Các bạn có thể dùng phân tích nguyên tố để tính UQ nhanh không?

    1 phản hồi

    • -4
      khoa2008    8:24 p.m. 11 Tháng 2, 2022

      Bài này rất hay nhưng mà cần sol ai viết sol đc ko???

      =(((((((
      
      1 phản hồi

      • 7
        huyhau6a2    7:57 p.m. 11 Tháng 2, 2022

        giải thích cho những ai chưa hiểu test:

          UQ(6)
            =UQ(3)+UQ(2)+UQ(1)
            =3+2+1
            =6
        
          UQ(20)
            =UQ(10)+UQ(5)+UQ(4)+UQ(2)+UQ(1)
            = (UQ(5)+UQ(2)+UQ(1)) +5+ (UQ(2)+UQ(1)) +2+1
            =5+2+1+5+2+1+2+1 
            =19
        
          UQ(36)
            =UQ(18)+UQ(12)+UQ(9)+UQ(6)+UQ(4)+UQ(3)+UQ(2)+UQ(1)
            = (UQ(9)+UQ(6)+UQ(3)+UQ(2)+UQ(1)) + (UQ(6)+UQ(4)+UQ(3)+UQ(2)+UQ(1)) + (UQ(3)+UQ(1)) + (UQ(3)+UQ(2)+UQ(1)) + (UQ(2)+UQ(1)) +3+2+1
            = (UQ(3)+UQ(1)) + (UQ(3)+UQ(2)+UQ(1)) +3+2+1+ (UQ(3)+UQ(2)+UQ(1)) + (UQ(2)+UQ(1)) +3+2+1+3+1+3+2+1+2+1+3+2+1
            =3+1+3+2+1+3+2+1+3+2+1+2+1+3+2+1+3+1+3+2+1+2+1+3+2+1
            =50