2024 · Tin học trẻ - Bảng B · Nam Quảng Trị

Với hai số nguyên dương ~a~ và ~b~, ta định nghĩa ~f(a,b) = \text{lcm}(a,b) - \gcd(a,b)~; trong đó ~\text{lcm}(a,b)~ là bội chung nhỏ nhất của hai số ~a~, ~b~ và ~\gcd(a,b)~ là ước chung lớn nhất của hai số ~a~, ~b~.

Input

• Dữ liệu được đọc từ file văn bản TIMHAISO.INP.
• Gồm một số nguyên ~n~ ~(2 \leq n \leq 10^9)~.

Output

• Ghi kết quả ra file văn bản TIMHAISO.OUT.
• Ghi ra một số nguyên dương cho biết kết quả của bài toán.

Scoring

Example input 1

6

Example output 1

4

Note 1

• ~f(a,b)~ có giá trị lớn nhất bằng ~4~ khi ~a=1~, ~b=5~ (hoặc ~a=5~, ~b=1~).

Cho dãy ~n~ số nguyên không âm ~a_1,a_2,\ldots,a_n~. Người ta tiến hành chọn ra hai chỉ số ~i~, ~j~ sao cho ~i<j~ và xoá khỏi dãy hai số ~a_i~, ~a_j~ để tổng giá trị các số còn lại trong dãy là số chẵn.</p>

Yêu cầu

Đếm số lượng cách chọn hai chỉ số ~i~, ~j~ thoả mãn. Hai cách chọn khác nhau nếu tồn tại một chỉ số khác nhau.

Input

• Dữ liệu được đọc từ file văn bản XOASO.INP.
• Dòng thứ nhất chứa số nguyên dương ~n~ (~2 \leq n \leq 10^6~).
• Dòng thứ hai chứa ~n~ số nguyên không âm ~a_1,a_2,\ldots,a_n~ (~0 \leq a_i \leq 10^9~, ~1 \leq i \leq n~). Các số cách nhau bởi dấu cách.

Output

• Ghi kết quả ra file văn bản XOASO.OUT.
• Ghi ra một số nguyên duy nhất cho biết số cách chọn hai chỉ số ~i~, ~j~ thoả mãn.

Scoring

Example input 1

5
1 2 3 4 5

Example output 1

6

Example input 2

5
2 4 6 8 10

Example output 2

10

Khi học về số nguyên tố, An phát hiện ra rằng có những số nguyên dương mà các ước thực sự (không kể ~1~ và chính nó) của nó đều là các số nguyên tố và An đã gọi những số này là số đẹp. Ví dụ ~10~ là một số đẹp vì có hai ước thực sự là ~2~ và ~5~ đều là các số nguyên tố. An có một người bạn rất thân vốn rất đam mê lập trình nên đã đặt ra bài toán cho bạn mình giải như sau: Cho dãy ~n~ số nguyên ~a_1,a_2,\ldots,a_n~ (~1 \leq n \leq 10^6~, ~1 \leq a_i \leq 2\times 10^7~). Hãy cho biết trong dãy số trên có bao nhiêu số đẹp?

Input

• Dữ liệu được đọc từ file văn bản SODEP.INP.
• Dòng thứ nhất chứa số nguyên ~n~ (~1 \leq n \leq 10^6~);
• Dòng thứ hai chứa ~n~ số nguyên ~a_1,a_2,\ldots,a_n~ (~1\leq a_i \leq 2\times 10^7~, ~1 \leq i \leq n~). Các số cách nhau bởi dấu cách.

Output

• Ghi kết quả ra file văn bản SODEP.OUT.

Scoring

Example input 1

9
9 7 10 6 17 4 19 21 23

Example output 1

5

Note 1

• Các số ~10~, ~6~, ~4~, ~21~ là các số đẹp.