Güclərin sayılması#12210

Güclərin sayılması (Həll təhlili)

Problemin Müəllifi:	Hasan Saleh (MathModel)
Hazırlayan:	Hasan Saleh (MathModel)
Redaktə edən:	Hasan Saleh (MathModel)

Həll Bütün $a, b$ cütlərini nəzərə alın ki, $a^{b}$ a^b hesablamaq istəyirik, çünki $a^{b}$ a^b çox böyük ola bilər və int və long long aralığından kənardadır, $a^{b} \equiv b lo g a$ a^b \equiv b \log a formasını istifadə edə bilərik, $b lo g a$ b \log a-nın bütün dəyərlərini çoxluğa $ms$ saxlaya bilərik, hər dəyər üçün hər element üçün neçə $a^{b}$ a^b olduğunu saymaq istəyirik, sonra sıralayırıq, hər giriş üçün ilk mövqeni $l$ üçün ikili axtarış edirik ki, $ms [l] \geq ms [k]$ \text{ms}[l] \ge \text{ms}[k] olsun, $∣ ms ∣ - l$ |\text{ms}|-l cütü $(c, d)$ var ki, $(a^{b} \leq c^{d})$ (a^b \le c^d) ümumilikdə $k$ .

Dəqiqlik problemlərinə diqqət edin!

#include <bits/stdc++.h>
using namespace std;
#define int long long

const long double EPS = 1e-15L;
vector<long double> logs(1001);
vector<vector<long double>> pre(1001);

void solve() {
    int n;
    cin >> n;

    vector<long double> ab;
    ab.reserve(n * n);
    for (int a = 1; a <= n; ++a)
        for (int b = 1; b <= n; ++b)
            ab.push_back(pre[a][b]);

    sort(ab.begin(), ab.end());

    long long res = 0;
    for (int c = 1; c <= n; ++c) {
        for (int d = 1; d <= n; ++d) {
            long double v = d * logs[c];
            res += upper_bound(ab.begin(), ab.end(), v + EPS) - ab.begin();
        }
    }

    cout << res << "\n";
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    for (int a = 1; a <= 1000; ++a) {
        logs[a] = logl(a);
        pre[a].resize(1001);
        for (int b = 1; b <= 1000; ++b) {
            pre[a][b] = b * logs[a];
        }
    }

    int t;
    cin >> t;
    while (t--) solve();
    return 0;
}

C++

Komplekslik $O (n^{2} lo g n)$ \mathcal{O}(n^2 \log n)