Информация об изменениях

Сообщение Re[2]: задачки с хедхантера от 13.10.2016 15:55

Изменено 13.10.2016 16:10 Lexey

Старый текст
Новый текст
Разница

Здравствуйте, Кодт, Вы писали:

К>У меня на питоне без особых оптимизаций это заняло 9 секунд. Ответ 324780928, надеюсь, что правильный.

Ты малость схалявил. Твой ответ верный, но для S(230000, 240000). А нужно было S(2300000, 2400000).

У меня получилось 27566064194.

Код

#include <cmath>
#include <vector>
#include <iostream>
#include <tuple>

using namespace std;

vector<int> primes({ 2, 3, 5, 7, 11, 13 });

void genPrimes(int max) {
    for (int n = 15; n <= max; n += 2) {
        auto it = primes.begin() + 1;
        for (;;) {
            if (it == primes.end()) {
                primes.push_back(n);
                break;
            }
            if (n % *it == 0) break;
            ++it;
        }
    }
}

int s(int n);

int main() {
    constexpr int m = 2300000;
    constexpr int n = 2400000;
    genPrimes(static_cast<int>(sqrt(n)));
    int64_t result = 0;
    for (auto i = m; i <= n; ++i)
    {
        result += s(i);
    }
    cout << result;
}

vector<tuple<int, int>> factorize(int n);
int factorial_power(int m, int p);

int s(int n)
{
    auto factors = factorize(n);
    int lb = 1;
    for (auto v: factors)
    {
        int p;
        int count;
        tie(p, count) = v;
        int lb_value = factorial_power(lb, p);
        if (lb_value >= count) continue;
        int ub = p * count;
        if (count < p)
        {
            lb = ub;
            continue;
        }
        while (lb < ub)
        {
            int median = lb + (ub - lb) / 2;
            int m_value = factorial_power(median, p);
            if (m_value < count)
            {
                lb = median + 1;
            }
            else
            {
                ub = median;
            }
        }
    }
    return lb;
}

int factorial_power(int m, int p)
{
    int result = 0;
    while (m >= p)
    {
        result += m / p;
        m /= p;
    }
    return result;
}

vector<tuple<int, int>> factorize(int n) {
    vector<tuple<int, int>> result;
    for (auto p : primes) {
        int count = 0;
        while (n % p == 0)
        {
            ++count;
            n /= p;
        }
        if (count > 0)
        {
            result.push_back(make_tuple(p, count));
        }
        if (p > n) break;
    }
    if (n > 1)
    {
        result.push_back(make_tuple(n, 1));
    }
    return result;
}

Работало секунд 25 в дебаге на рабочей машинке средней дохлости. При желании есть куда оптимизировать.

У меня получилось 27566064194.

Код

#include <cmath>
#include <vector>
#include <iostream>
#include <tuple>

using namespace std;

vector<int> primes({ 2, 3, 5, 7, 11, 13 });

void genPrimes(int max) {
    for (int n = 15; n <= max; n += 2) {
        auto it = primes.begin() + 1;
        for (;;) {
            if (it == primes.end()) {
                primes.push_back(n);
                break;
            }
            if (n % *it == 0) break;
            ++it;
        }
    }
}

int s(int n);

int main() {
    constexpr int m = 2300000;
    constexpr int n = 2400000;
    genPrimes(static_cast<int>(sqrt(n)));
    int64_t result = 0;
    for (auto i = m; i <= n; ++i)
    {
        result += s(i);
    }
    cout << result;
}

vector<tuple<int, int>> factorize(int n);
int factorial_power(int m, int p);

int s(int n)
{
    auto factors = factorize(n);
    int lb = 1;
    for (auto v: factors)
    {
        int p;
        int count;
        tie(p, count) = v;
        int lb_value = factorial_power(lb, p);
        if (lb_value >= count) continue;
        int ub = p * count;
        if (count < p)
        {
            lb = ub;
            continue;
        }
        while (lb < ub)
        {
            int median = lb + (ub - lb) / 2;
            int m_value = factorial_power(median, p);
            if (m_value < count)
            {
                lb = median + 1;
            }
            else
            {
                ub = median;
            }
        }
    }
    return lb;
}

int factorial_power(int m, int p)
{
    int result = 0;
    while (m >= p)
    {
        result += m / p;
        m /= p;
    }
    return result;
}

vector<tuple<int, int>> factorize(int n) {
    vector<tuple<int, int>> result;
    for (auto p : primes) {
        int count = 0;
        while (n % p == 0)
        {
            ++count;
            n /= p;
        }
        if (count > 0)
        {
            result.push_back(make_tuple(p, count));
        }
        if (p > n) break;
    }
    if (n > 1)
    {
        result.push_back(make_tuple(n, 1));
    }
    return result;
}

В релизе 137 мс.

И можно поотимизировать еще.