Pre TS10 2023 #01 - Tổng ước chung lớn nhất

Xem PDF
Nộp bài
Điểm: 1500 (thành phần)
Thời gian: 1.0s
Bộ nhớ: 256M
Input: SGCD.inp
Output: SGCD.out
Tác giả:
Sunlight
Dạng bài
Ngôn ngữ cho phép
C++, NASM, Pascal, pypy3, Python, text

Cho hai số nguyên dương n, m. Tính tổng các giá trị gcd(i, j) với mọi 1 \le i \le n và 1 \le j \le m.

Input, Output và Subtasks

Input: (SGCD.inp)
  • Một dòng duy nhất gồm hai số nguyên dương n, m (n, m \le 2 \times 10^6)
Output: (SGCD.out)
  • Một số nguyên duy nhất là kết quả bài toán.
Subtasks
  • Subtask 1 (40\%): n, m \le 2000
  • Subtask 2 (30\%): n, m \le 2 \times 10^5.
  • Subtask 3 (30\%): Không có giới hạn gì thêm.

Sample

Input (SGCD.inp) 
3 4
Output (SGCD.out) 
16
Note
  • gcd(1, 1) = gcd(1, 2) = gcd(1, 3) = gcd(1, 4) = 1
  • gcd(2, 1) = gcd(2, 3) = 1, gcd(2, 2) = gcd(2, 4) = 2.
  • gcd(3, 1) = gcd(3, 2) = gcd(3, 4) = 1, gcd(3, 3) = 3.

Bình luận