Conteo de potencias (Editorial)

Conteo de potencias#12210

Autor del problema:	Hasan Saleh (MathModel)
Preparado por:	Hasan Saleh (MathModel)
Editado por:	Hasan Saleh (MathModel)

Solución Considera todos los pares $a, b$ tal que queremos calcular $a^{b}$ a^b, dado que $a^{b}$ a^b puede ser demasiado grande y está fuera del rango de int y long long, podemos usar la forma de $a^{b} \equiv b lo g a$ a^b \equiv b \log a, podemos almacenar todos los valores de $b lo g a$ b \log a en un multiconjunto $ms$ , para cada valor queremos contar cuántos $a^{b}$ a^b hay, luego ordenarlo, para cada entrada buscar binariamente la primera posición $l$ tal que $ms [l] \geq ms [k]$ \text{ms}[l] \ge \text{ms}[k], hay $∣ ms ∣ - l$ |\text{ms}|-l pares $(c, d)$ tales que $(a^{b} \leq c^{d})$ (a^b \le c^d) en total $k$ .

¡Ten cuidado con los problemas de precisión!

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

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