\(\color{red}{\text{Spoiler Alert}_{{}_{{}^{{}^{v2.0}}}}}\)

\(\color{red}{\text{Khuyến khích bạn đọc trước khi đọc phần lời giải xin hãy thử code ra thuật của mình dù nó có sai hay đúng}}\)

\(\color{red}{\text{Sau đó từ phần bài giải và thuật toán trước đó mà đối chiếu, rút nhận xét với thuật của mình và thu được bài học (không lãng phí thời gian đâu).}}\)

\(\color{orange}{\text{Hint 1 <Brute-forces>}}\)

• Bài toán quy về dạng đếm số lượng số \(2 \leq gn \leq m; 1 \leq k \leq m\) thỏa \(k \leq n \times gn\)

Ta sẽ duyệt trâu từng phần tử \((k, gn)\) và kiểm tra xem nó có thỏa mãn không

\(\color{green}{\text{Preference TLE Code }}\): Brute-forces

\(^{^{\color{purple}{\text{Complexity : }} O(m ^ 2)\ \color{purple}{\text{time}}\ ||\ O(1)\ \color{purple}{\text{memory}}}}\)

int main()
{
    ll m, n;
    cin >> m >> n;

    ll total = 0;
    ll res = 0;    
    for (ll gn = 2; gn <= m; ++gn)
    {
        for (ll k = 1; k <= m; ++k)
        {
             res += k <= (n * gn);
             total++;
        }
    }

    cout << setprecision(8) << fixed << db(res) / total;
    return 0;
}

\(\color{orange}{\text{Hint 2 <Simple-Math>}}\)

• Số \(gn\) có \(m - 1\) cách chọn, \(k\) có \(m\) cách chọn

Ta có \(total = m \times (m - 1)\)

• Với mỗi số \(gn\) cố định, ta cần đếm số lượng \(k \in [1, m]\) thỏa \(k \leq gn * n\)

Có \(gn \times n\) cách chọn khi \(gn \times n \leq m\)

Có \(m\) cách chọn khi \(gn \times n \geq m\)

Vậy có tổng cộng \(min(m, gn \times n)\) cách chọn số \(k\) với mỗi \(gn\) cố định

\(\color{green}{\text{Preference TLE Code }}\): Simple Math

\(^{^{\color{purple}{\text{Complexity : }} O(m)\ \color{purple}{\text{time}}\ ||\ O(1)\ \color{purple}{\text{memory}}}}\)

int main()
{
    ll m, n;
    cin >> m >> n;

    ll total = (m - 1) * m;
    ll res = 0;
    for (ll gn = 2; gn <= m; ++gn)
        res += min(m, gn * n);

    cout << setprecision(8) << fixed << db(res) / total;
    return 0;
}

\(\color{orange}{\text{Hint 2 <Math>}}\)

• Khi \(gn < \lceil \frac{m}{n} \rceil\) thì có \(gn \times n\) cách chọn

Tổng số cách chọn là \((2 + 3 + .. + m) \times n\)

• Khi \(gn \geq \lceil \frac{m}{n} \rceil\) thì có \(m\) cách chọn

Tổng số cách chọn là \(\frac{m - \lceil \frac{m}{n} \rceil + 1}{m - 1}\)

• Đặt \(t = \lceil \frac{m}{n} \rceil = \lfloor \frac{m + n - 1}{n} \rfloor\)

Tổng số cách chọn thỏa mãn: \(res = (m - t + 1) \times m + (\frac{t \times (t - 1)}{2} - 1) \times n\)

\(\color{green}{\text{Preference WA Code }}\): Math

\(^{^{\color{purple}{\text{Complexity : }} O(1)\ \color{purple}{\text{time}}\ ||\ O(1)\ \color{purple}{\text{memory}}}}\)

int main()
{
    ll m, n;
    cin >> m >> n;

    ll t = (m + n - 1) / n;
    ll total = (m - 1) * m;
    ll res = (m - t + 1) * m + (t * (t - 1) / 2 - 1) * n;

    cout << setprecision(8) << fixed << db(res) / total;
    return 0;
}

\(\color{orange}{\text{Hint 3 <Optimized-Math>}}\)

• Có \(\frac{k}{gn} \leq \frac{m}{2}\)

Khi \(\frac{m}{2} \leq {n}\) thì số cặp\((k, gn)\) thỏa mãn \(=\) số cách chọn nên xác xuất là \(1\)

• Dùng kiểu dữ liệu thực (C++) dể lưu số lớn hơn và việc nhân nhau ra số lớn thì ta chia nó để cho nó gọn hơn

Có \(\frac{res}{total} = \frac{(m - t + 1) \times m + (\frac{t \times (t - 1)}{2} - 1) \times n}{m * (m - 1)} = \frac{m - t + 1}{m - 1} + \frac{\frac{t \times (t - 1)}{2} - 1}{m} \times \frac{n}{m - 1}\)

\(\color{green}{\text{Preference AC Code }}\): Math

\(^{^{\color{purple}{\text{Complexity : }} O(1)\ \color{purple}{\text{time}}\ ||\ O(1)\ \color{purple}{\text{memory}}}}\)

int main()
{
    ll m, n;
    cin >> m >> n;

    ll t = (m + n - 1) / n;
    double res;
    if (m <= n * 2)
        res = 1;
    else
        res = double(m - t + 1) / (m - 1) + double(t * double(t - 1) / 2 - 1) / m * double(n) / (m - 1);

    cout << setprecision(8) << fixed << res;
    return 0;
}