CSES - Divisor Analysis | Phân tích ước số

Xem PDF
Tất cả bài nộp
Các bài nộp tốt nhất
Tác giả:
Flower_On_Stone , kitsune , SPyofgame , Only_Avocado
Dạng bài
Điểm: 1600 (p) Thời gian: 1.0s Bộ nhớ: 512M Input: bàn phím Output: màn hình

Cho một số nguyên, nhiệm vụ của bạn là tìm số lượng, tổng và tích của các ước số của nó. Ví dụ, chúng ta hãy xem xét số \(12\):

  • số lượng ước số là \(6\) (chúng là \(1 , 2, 3, 4, 6, 12\))
  • tổng của các ước số là \(1 + 2 + 3 + 4 + 6 + 12 = 28\)
  • tích của các ước số là \(1 \cdot 2 \cdot 3 \cdot 4 \cdot 6 \cdot 12 = 1728\)

Vì số đầu vào có thể rất lớn, nó sẽ được cho dưới dạng phân tích thừa số nguyên tố.

Input

  • Dòng đầu tiên có một số nguyên \(n\): số phần trong dạng phân tich thừa số nguyên tố.
  • Sau đó, gồm \(n\) dòng mô tả dạng phân tích. Mỗi dòng có hai số \(x\) và \(k\), trong đó \(x\) là số nguyên tố và \(k\) là lũy thừa của nó.

Output

  • In ba số nguyên chia lấy dư cho \(10 ^ 9 + 7\): số lượng, tổng và tích của các ước số.

Constraints

  • \(1 \leq n \leq 10^5\)
  • \(2 \leq x \leq 10^6\)
  • mỗi \(x\) là một số nguyên tố riêng biệt
  • \(1 \leq k \leq 10^9\)

Example

Sample input

2 
2 2
3 1

Sample output

6 28 1728

Bình luận


  • 1
    N7hoatt    9:52 a.m. 30 Tháng 8, 2023

    Với một số nguyên cho trước, hãy tìm số lượng, tổng và tích của các ước số của nó. Ví dụ, số được cho là \(12\):

    • Số lượng ước số là \(6\) (đó là \(1,2,3,4,6,12\)).
    • Tổng các ước số là \(1+2+3+4+6+12=28\).
    • Tích các ước số là \(1\times2\times3\times4\times6\times12=1728\).

    Vì số được cho có thể rất lớn nên nó sẽ được cho dưới dạng tích thừa số nguyên tố.

    Input

    • Dòng đầu tiên chứa số nguyên \(n\): số lượng thành phần trong tích thừa số nguyên tố.
    • \(n\) dòng tiếp theo mỗi dòng gồm hai số nguyên \(x\) và \(k\): \(x\) là số nguyên tố và \(k\) là số mũ của nó.

    Output

    • In ra ba số nguyên mod \(10^9+7\): số lượng, tổng và tích của các ước số.

    Constraints

    • \(1 \leq n \leq 10^5\).
    • \(2 \leq x \leq 10^6\).
    • Mỗi số x đều là một số nguyên tố phân biệt.
    • \(1 \leq k \leq 10^9\).

    Example

    Test

    Input 
    2
2 2
3 1
    Output 
    6 28 1728
    Note

    • 0
      minh122k2q    4:34 p.m. 12 Tháng 2, 2024

      Sao ko có note vậy?

      1 bình luận nữa