sumGCD
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];
Ví Dụ:
- Với
n = 4thìsumGCD(n) = 7giải thích :F[4] = gcd(1, 2) + gcd(1, 3) + gcd(1, 4) + gcd(2, 3) + gcd(2, 4) + gcd(3, 4) = 7;
Đầu vào/Đầu ra:
- [Thời gian] 0.5s với C++, 3s với Java và C#, 4s với Python, Go và JavaScript.
- [Đầu vào] integer n
1 <= n <= 10^6 - [Đầu ra] long
Tổng các ước chung nhỏ nhất xác định bởi hàm F(n)
Post Comment