Powers counting#12210

Powers counting (Анализа на решението)

Problem Author:	Hasan Saleh (MathModel)
Prepared by:	Hasan Saleh (MathModel)
Edited by:	Hasan Saleh (MathModel)

Solution Consider all pairs $a, b$ such we want to compute $a^{b}$ a^b , since $a^{b}$ a^b maybe too large and is out of int and long long range , we can use the form of $a^{b} \equiv b lo g a$ a^b \equiv b \log a , we can store all values of $b lo g a$ b \log a to multiset $ms$ , for each value we want to count for each element how many $a^{b}$ a^b then sort it , for each entry binary search for the first position $l$ such $ms [l] \geq ms [k]$ \text{ms}[l] \ge \text{ms}[k] there are $∣ ms ∣ - l$ |\text{ms}|-l pairs $(c, d)$ such $(a^{b} \leq c^{d})$ (a^b \le c^d) overall $k$ .

Be aware of precision issues !

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

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