Editorial for Bedan Contest #05 - B - Tổng GCD


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.

Submitting an official solution before solving the problem yourself is a bannable offence.

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).


Comments

There are no comments at the moment.