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

View as PDF



Authors:
Problem types
Points: 1700 (p) Time limit: 1.0s Memory limit: 512M Input: stdin Output: stdout

Given a list of \(n\) positive integers, your task is to count the number of pairs of integers that are coprime (i.e., their greatest common divisor is one).

Input

  • The first input line has an integer \(n\): the number of elements.
  • The next line has \(n\) integers \(x_1,x_2,\dots,x_n\): the contents of the list.

Output

  • Print one integer: the answer for the task.

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


Comments

  • hnhbinhnd 10:58 a.m. 2 sep, 2024
    • N7hoatt 9:35 p.m. 31 aug, 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