Підрахунок степенів#12210

Підрахунок степенів (Розбір)

Автор проблеми:	Хасан Салех (MathModel)
Підготовлено:	Хасан Салех (MathModel)
Редаговано:	Хасан Салех (MathModel)

Рішення Розглянемо всі пари $a, b$ , для яких ми хочемо обчислити $a^{b}$ a^b, оскільки $a^{b}$ a^b може бути занадто великим і виходити за межі int і long long, ми можемо використовувати форму $a^{b} \equiv b lo g a$ a^b \equiv b \log a, ми можемо зберігати всі значення $b lo g a$ b \log a в мультисет $ms$ , для кожного значення ми хочемо підрахувати, скільки $a^{b}$ a^b, потім відсортуємо його, для кожного запису бінарно шукаємо першу позицію $l$ , таку що $ms [l] \geq ms [k]$ \text{ms}[l] \ge \text{ms}[k], є $∣ ms ∣ - l$ |\text{ms}|-l пар $(c, d)$ таких, що $(a^{b} \leq c^{d})$ (a^b \le c^d) загалом $k$ .

Будьте обережні з проблемами точності!

#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++

Складність $O (n^{2} lo g n)$ \mathcal{O}(n^2 \log n)