Comptage des puissances#12210

Comptage des puissances (Corrigé)

Auteur du problème :	Hasan Saleh (MathModel)
Préparé par :	Hasan Saleh (MathModel)
Édité par :	Hasan Saleh (MathModel)

Solution Considérez toutes les paires $a, b$ pour lesquelles nous voulons calculer $a^{b}$ a^b, puisque $a^{b}$ a^b peut être trop grand et hors de portée des types int et long long, nous pouvons utiliser la forme de $a^{b} \equiv b lo g a$ a^b \equiv b \log a, nous pouvons stocker toutes les valeurs de $b lo g a$ b \log a dans un multiset $ms$ , pour chaque valeur nous voulons compter pour chaque élément combien de $a^{b}$ a^b, puis trier, pour chaque entrée effectuer une recherche binaire pour la première position $l$ telle que $ms [l] \geq ms [k]$ \text{ms}[l] \ge \text{ms}[k], il y a $∣ ms ∣ - l$ |\text{ms}|-l paires $(c, d)$ telles que $(a^{b} \leq c^{d})$ (a^b \le c^d) au total $k$ .

Faites attention aux problèmes de précision !

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

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