Функция Эйлера. time-limit-exceeded

Question

Программа реализует функцию Эйлера (https://ru.wikipedia.org/wiki/Функция_Эйлера), вроде всё работает, на тестах проверял - ошибок не возникало на достаточно больших числах в том числе.

Единственная проблема - не могу сдать программу ввиду time-limit-exceeded (на первых 9 тестах всё работает за 2 миллисекунды, а на 10-м тесте - 3.076 секунду). Макс. ограничение во времени - 3 секунды. Прошу помочь, может кто найдет где у меня в программе это может происходить?

#include <iostream>
using namespace std;

int binomialCoeff(int k, int n)  
{ 
    if (k == 0 || k == n)  
        return 1;  
  
    return binomialCoeff(k - 1, n - 1) +  
        binomialCoeff(k, n - 1);  
}

int gsd(int a, int b) {
    while(a!=0 && b!=0) {
        if(a>b) a%=b;
        else b%=a;
    }
    return a+b;
}

int Euler(unsigned long k, unsigned long n) {
    unsigned int result=1; 
    int combination = binomialCoeff(k,n);
    for(int i=2; i<=combination; i++) {
        if(gsd(i,combination) == 1) {
            result++;
        }
    }
    return result;
}

int main() {
    int k, n;
    cin >> k >> n;
    if(k<0 || n<0 || n<k) 
        throw invalid_argument("Binom condition failed");
    cout << Euler(k,n);
    return 0;
}

Answer 1

Что-то как-то странно вы ее вычисляете... И потом, что-то я по ссылке не нашел никакой функции Эйлера от двух переменных. Так что уточните, о том ли я отвечаю, о чем вы спрашиваете? :)

Недавно пришлось писать ее на Python, вот перевод на C/C++:

unsigned long long fi(unsigned long long n)
{
    unsigned long long f = n;
    if (n%2 == 0)
    {
        while (n%2 == 0) n /= 2;
        f/= 2;
    }
    for(unsigned long long i = 3; i*i <= n; i += 2)
    {
        if (n%i == 0)
        {
            while (n%i == 0) n /= i;
            f /= i;
            f *= (i-1);
        }
    }
    if (n > 1)
    {
        f /= n;
        f *= (n-1);
    }
    return f;
}

Это то, что вам нужно?

На таком неприятном числе, как 187917426909946969 (квадрат простого числа, т.е. полный перебор), у меня на машине работает примерно 1.61±0.02 с.

Answer 2

int binomialCoeff(int k, int n)
{ 
    if (k == 0 || k == n)  
        return 1;  
  
    return binomialCoeff(k - 1, n - 1) +  
        binomialCoeff(k, n - 1);  
}

У этой функции экспоненциальная сложность. Вместо этого лучше считать по формуле.

Answer 3

Функция Эйлера от биномиального коэффициента φ(cnk(n, k)) вычисляется без нахождения самого коэффициента. Надо перебрать все простые, для каждого простого числа найти степень с которой оно входит в биномиальный коэффициент. Коэффициент - комбинация трёх факториалов cnk(n, k) = n! / (k! * (n - k)!). Для факториала степень простого находится просто:

// степень s такая что n! делится на p^s, но не делится на p^(s + 1)
unsigned factorial_exponent(unsigned n, unsigned p) {
    // assert(is_prime(p));
    unsigned e = 0;
    for (unsigned t = n / p; t > 0; t /= p) {
        e += t;
    }
    return e;
}

Для биномиального коэффициента:

// степень s такая что cnk(n, k) делится на p^s, но не делится на p^(s + 1)
unsigned binomial_exponent(unsigned n, unsigned k, unsigned p) {
    return factorial_exponent(n, p) -
           (factorial_exponent(k, p) + factorial_exponent(n - k, p));
}

Вычисление φ(cnk(n, k)) выполняется по разложению на простые:

// phi(cnk(n, k))
uint64_t phi_cnk(unsigned n, unsigned k) {
    product_t phi = 1;

    for (primes_t it(n + 1); it; ++it) {
        const unsigned p = *it;
        const unsigned e = binomial_exponent(n, k, p);
        if (e > 0) {
            phi *= p - 1;
            for (unsigned i = 0; i < e - 1; ++i) {
                phi *= p;
            }
        }
    }
    return phi;
}

Вся программа довольно большая - нужны решето Эратосфена, извлечение квадратного корня и контроль переполнения при умножении:

#include <cmath>
#include <iostream>
#include <limits>
#include <stdexcept>
#include <vector>

unsigned isqrt(unsigned a) {
    unsigned low = 0;
    unsigned high = std::min(
        1U << (std::numeric_limits<unsigned>::digits / 2),
        a / 2U + 2
    ); 

    while (low < high - 1) {
        const unsigned mid = (high + low) / 2U;
        if (mid * mid > a) {
            high = mid;
        } else {
            low = mid;
        }
    }
    return low;
}

class primes_t {
public:
    primes_t(unsigned n) : n(n), sqrt_n(isqrt(n)), sieve(n, true), i(2) {}
    operator bool() const { return i < n; }
    unsigned operator *() const { return i; }

    primes_t &operator ++() {
        if (i <= sqrt_n) {
            for (unsigned j = i * i; j < n; j += i) {
                sieve[j] = false;
            }
        }

        for (++i; i < n; ++i) {
            if (sieve[i]) {
                return *this;
            }
        }

        i = n;
        return *this;
    }

private:
    unsigned n;
    unsigned sqrt_n;
    std::vector<bool> sieve;
    unsigned i;
};

unsigned factorial_exponent(unsigned n, unsigned p) {
    // assert(is_prime(p));
    unsigned e = 0;
    for (unsigned t = n / p; t > 0; t /= p) {
        e += t;
    }
    return e;
}

unsigned binomial_exponent(unsigned n, unsigned k, unsigned p) {
    return factorial_exponent(n, p) -
           (factorial_exponent(k, p) + factorial_exponent(n - k, p));
}

class product_t {
public:
    product_t(unsigned product) : product(product) {}
    void operator *=(unsigned factor) {
        if (std::numeric_limits<uint64_t>::max() / product < factor) {
            throw std::overflow_error("overflow");
        }
        product *= factor;
    }
    operator uint64_t() const { return product; }
private:
    uint64_t product;
};

uint64_t phi_cnk(unsigned n, unsigned k) {
    product_t phi = 1;

    for (primes_t it(n + 1); it; ++it) {
        const unsigned p = *it;
        const unsigned e = binomial_exponent(n, k, p);
        if (e > 0) {
            phi *= p - 1;
            for (unsigned i = 0; i < e - 1; ++i) {
                phi *= p;
            }
        }
    }
    return phi;
}

int main() {
    unsigned n, k;
    if (!(std::cin >> n >> k)) {
        std::cerr << "input error\n";
        return 1;
    }
    uint64_t phi;
    try {
        phi = phi_cnk(n, k);
    } catch (const std::overflow_error &e) {
        std::cerr << "overflow\n";
        return 1;
    }
    std::cout << phi << '\n';
}

$ g++ -std=c++17 -pedantic -Wall -Wextra -Werror -O3 phi-cnk.cpp 

$ echo 69 34 | ./a.out
11368549725319987200

$ time echo 1000000000 2 | ./a.out
129729340800000000

real  0m10.228s
user  0m10.188s
sys   0m0.036s

БЛОГ НА HUSL

Функция Эйлера. time-limit-exceeded

Ответы (3 шт):