CSES - Counting Coprime Pairs | Đếm cặp số nguyên tố cùng nhau

Xem PDF



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

Cho một danh sách \(n\) số nguyên dương, nhiệm vụ của bạn là đếm số cặp số nguyên mà nguyên tố cùng nhau (tức là, ước số chung lớn nhất của chúng là một).

Input

  • Dòng đầu vào đầu tiên có một số nguyên \(n\): số lượng phần tử.
  • Dòng tiếp theo có \(n\) số nguyên \(x_1, x_2, ... ,x_n\): nội dung của danh sách.

Output

  • In một số nguyên: câu trả lời cho nhiệm vụ.

Constraints

  • \(1 \leq n \leq 10^5\)
  • \(1 \leq x_i \leq 10^6\)

Example

Sample input

8
5 4 20 1 16 17 5 15

Sample output

19


Bình luận


  • 0
    N7hoatt 9:35 p.m. 31 Tháng 8, 2023

    Bạn được cho một danh sách gồm \(n\) số nguyên dương, hãy đếm số cặp số nguyên tố cùng nhau (ước chung lớn nhất của chúng là một).

    Hãy đếm trong \(n\) số nguyên dương đầu tiên, có bao nhiêu số chia hết cho ít nhất một số trong các số nguyên tố được cho.

    Input

    • Dòng đầu tiên gồm một số nguyên \(n\): số lượng phần tử.
    • Dòng thứ hai gồm \(n\) số nguyên \(x_1,x_2,x_3,\dots,x_n\).

    Output

    • In một số nguyên: kết quả của bài toán.

    Constraints

    • \(1 \leq n \leq 10^5\).
    • \(2 \leq a_i \leq 10^6\).

    Example

    Test 1

    Input
    8
    5 4 20 1 16 17 5 15
    Output
    19
    Note