SUMGCD - SUMGCD
Dữ liệu vào: standard input
Dữ liệu ra: standard output
Giới hạn thời gian: 1.0 giây
Giới hạn bộ nhớ: 128 megabyte
Đăng bởi: nghethuat102

Gọi gcd(x, y) là ước chung lớn nhất của 2 số x và y; F[n] là tổng gcd(i, j) với 1 <= i, j <= n và i < j;

Yêu cầu: tính F[n];

Dữ liệu vào: 

  • Dòng đầu chứa số T (T <= 100000) là số test;
  • Dòng thứ 2 đến T + 1, mỗi dòng chứa số N (1 <= N <= 1000000);

Xuất ra: 

  • gồm T dòng là kết quả tương ứng.

Nguồn bài: (ACM World Final Warm up 1 - 2008) 

Ví dụ

  • input
    5
    1
    2
    3
    4
    5
    output
    0
    1
    3
    7
    11

giải thích: F[4] = gcd(1, 2) + gcd(1, 3)  + gcd(1, 4) + gcd(2, 3) + gcd(2, 4) + gcd(3, 4) = 7;

Back to Top