verify/unit_test/shifted_array.test.cpp

• View this file on GitHub
• Last update: 2025-09-29 18:40:17+09:00
• Problem: https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2858

Depends on

• utilities/shifted_array.hpp

Code

#define PROBLEM "https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2858"

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

#include "../../utilities/shifted_array.hpp"

constexpr long long MAX = 100000;

long long solve(long long l, long long r) {
    vector<char> is_prime(MAX, 1);
    is_prime[0] = is_prime[1] = 0;
    m1une::shifted_array<vector<long long>> prime_factors(l, r);
    for (long long p = 2; p * p <= r; ++p) {
        if (!is_prime[p]) continue;
        for (long long x = 2 * p; x < MAX; x += p) {
            is_prime[x] = 0;
        }
        for (long long x = (l + p - 1) / p * p; x <= r; x += p) {
            prime_factors[x].emplace_back(p);
        }
    }
    long long res = 0;
    for (long long x = l; x <= r; ++x) {
        long long factor_count = 0;
        long long y = x;
        for (long long p : prime_factors[x]) {
            while (y % p == 0) {
                y /= p;
                ++factor_count;
            }
        }
        if (y > 1) {
            ++factor_count;
        }
        if (is_prime[factor_count]) {
            ++res;
        }
    }
    return res;
}

int main() {
    long long l, r;
    cin >> l >> r;
    cout << solve(l, r) << endl;
}

#line 1 "verify/unit_test/shifted_array.test.cpp"
#define PROBLEM "https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2858"

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

#line 1 "utilities/shifted_array.hpp"



#line 6 "utilities/shifted_array.hpp"

namespace m1une {
// bool is not allowed
// if you want to use bool, use char instead
template <typename T>
struct shifted_array {
   private:
    long long _offset;
    long long _step;
    int _size;
    std::vector<T> _data;

   public:
    // make an array with indices from L to R (including both L and R)
    // [L, R] (closed interval)
    shifted_array(long long L, long long R, T init_value = T(), long long step = 1)
        : _offset(L), _step(step), _size((R - L) / step + 1), _data(_size, init_value) {
        if (step <= 0) {
            throw std::invalid_argument("Step must be positive");
        }
        if (L > R) {
            throw std::invalid_argument("Left bound must be less than or equal to right bound");
        }
    }
    T &operator[](long long i) {
        int index = (i - _offset) / _step;
        if (index < 0 || index >= _size) {
            throw std::out_of_range("Index out of range");
        }
        return _data[index];
    };
    const T &operator[](long long i) const {
        int index = (i - _offset) / _step;
        if (index < 0 || index >= _size) {
            throw std::out_of_range("Index out of range");
        }
        return _data[index];
    };
    long long index(long long i) const {
        int index = (i - _offset) / _step;
        if (index < 0 || index >= _size) {
            throw std::out_of_range("Index out of range");
        }
        return index;
    }
};

}  // namespace m1une


#line 7 "verify/unit_test/shifted_array.test.cpp"

constexpr long long MAX = 100000;

long long solve(long long l, long long r) {
    vector<char> is_prime(MAX, 1);
    is_prime[0] = is_prime[1] = 0;
    m1une::shifted_array<vector<long long>> prime_factors(l, r);
    for (long long p = 2; p * p <= r; ++p) {
        if (!is_prime[p]) continue;
        for (long long x = 2 * p; x < MAX; x += p) {
            is_prime[x] = 0;
        }
        for (long long x = (l + p - 1) / p * p; x <= r; x += p) {
            prime_factors[x].emplace_back(p);
        }
    }
    long long res = 0;
    for (long long x = l; x <= r; ++x) {
        long long factor_count = 0;
        long long y = x;
        for (long long p : prime_factors[x]) {
            while (y % p == 0) {
                y /= p;
                ++factor_count;
            }
        }
        if (y > 1) {
            ++factor_count;
        }
        if (is_prime[factor_count]) {
            ++res;
        }
    }
    return res;
}

int main() {
    long long l, r;
    cin >> l >> r;
    cout << solve(l, r) << endl;
}

Back to top page