Hướng dẫn cho Bedan Contest #05 - B - Tổng GCD

Chỉ sử dụng khi thực sự cần thiết như một cách tôn trọng tác giả và người viết hướng dẫn này.

Chép code từ bài hướng dẫn để nộp bài là hành vi có thể dẫn đến khóa tài khoản.

Authors: flo

Cách giải

Hint

Dễ dàng thấy $\sum_{i = 1}^n gcd(i, p_{n-i+1})$ đạt giá trị nhỏ nhất là $n$ , khi đó thì $gcd(i, p_{n-i+1}) = 1$ với mọi $1 \le i \le n$ .

Solution

Ta đặt $p_1 = 1$ và khi đó $p_n$ có thể nhận bất kì giá trị nào.
Với $2 \le i \le n$ , ta có nhận xét $gcd(x, x+1) = 1$ . Từ nhận xét đó, ta có thể đặt $p_{n-i+1} = i+1$ .
Từ điều số $2$ , ta dễ dàng thấy dãy $(p_2, p_3, ..., p_n)$ là một dãy giảm nên sẽ thỏa mãn điều kiện số $1$ là có một cặp nghịch thế $(i, j)$ .
Độ phức tạp của ý tưởng trên là $O(n)$ .

Bình luận

Không có bình luận nào.