Найти минимальное число, факториал которого будет делиться на определенное число

@sapbufer · Регистрация: 27.11.2014

Author24 — интернет-сервис помощи студентам

здравствуйте,есть задача, в ходе которой нужно найти минимальное число m, факториал которого будет делится на определенное число к.
т.е. если k = 6, m = 3; k = 10; m = 5;
работа идет с числами от 810 000 000 до 820 000 000, нужна сумма всех чисел m для чисел этого промежутка.
какой самый оптимальный вариант решения этой задачи?
написал когда, но он слишком долго работает.

Кликните здесь для просмотра всего текста

C#

 
           ulong sum1 = 0;
            for (int u = 840000000; u <= 850000000; u++)
            {
 
                    
                sum1 += (ulong)func1(prost(u));
            }
private int func1(List<int> x)
        {
            x.Sort();
            int k = 1;
            int l = 0;
            int fact = 0;
            foreach(int xi in x)
            {
                if (k != xi)
                {
                    
                    int fact1=0;
                    int i = 0;
                    while(l>0)
                    {
                        fact1 += k;
                        i++;
                        if (i % k == 0)
                            l -= (i / k + 1);
                        else
                            l -= 1;
 
                    }
                    fact = fact < fact1 ? fact1 : fact;
                    k = xi;
                    l = 1;
                }
 
                else
                {
                    l++;
                }
            }
            int fact2 = 0;
            int ii = 0;
            while (l > 0)
            {
                fact2 += k;
                ii++;
                if (ii % k == 0)
                    l -= (ii / k + 1);
                else
                    l -= 1;
 
            }
            fact = fact < fact2 ? fact2 : fact;
            return fact;
        }
        private List<int> prost(int x)
        {
            List<int> prostlist = new List<int>();
            if (x == 1)
            {
                prostlist.Add(1);
                return prostlist;
            }
            for (int i = 2; i <= x; i++)
                if (x % i == 0)
                {
                    prostlist.Add(i);
                    x /= i;
                    List<int> newprost = prost(x);
                    foreach (int y in newprost)
                        prostlist.Add(y);
                    break;
                }
            while (prostlist.Contains(1))
                prostlist.Remove(1);
            return prostlist;
 
        }

@Shamil1 · 20.09.2016, 17:53

У меня получается 14144.

Вот простой вариант:

C#

long Solve(long maxn, int maxpow)
{
    var bit = new BitArray((int)maxn);
    var set = new HashSet<int>();
    long count = 0;
    for (long n = 2; n < maxn; n++)
    {
        if (bit[(int)n])
            continue;
        set.Clear();
        long p = 1;
        for (int k = 1; ; k++)
        {
            p *= n;
            if (p >= maxn)
                break;
            bit[(int)p] = true;
            for (int pow = 3; pow < maxpow; pow++)
            {
                var pk = pow * k;
                if (p != 2 && !set.Contains(pk))
                    set.Add(pk);
            }
        }
        count += set.Count;
    }
    return count;
}

Вместе с числом сразу обрабатываем все его степени. Обработанные числа "отмечаем" в битовом массиве.
Цикл начинаем с 2, чтобы обработать все степени двойки.

Его можно оптимизировать:
1. Начинать цикл в строке 12 с k = 2, а для k = 1 сразу добавлять count += maxpow - 3;
2. После этого цикл в строке 12 становится ненужным для n > sqrt(maxn)

Вот оптимизированный вариант:

C#

long OptimizedSolve(long maxn, int maxpow)
{
    var sqrt = (long)Math.Ceiling(Math.Sqrt(maxn));
    if (sqrt < 3)
        sqrt = 3;
    var bit = new BitArray((int)maxn);
    var set = new HashSet<int>();
    long count = 0;
    for (long n = 2; n < sqrt; n++)
    {
        if (bit[(int)n])
            continue;
        set.Clear();
        if (n > 2)
            count += maxpow - 3;
        var p = n;
        for (int k = 2; ; k++)
        {
            p *= n;
            if (p >= maxn)
                break;
            bit[(int)p] = true;
            for (int pow = 3; pow < maxpow; pow++)
            {
                var pk = pow * k;
                if ((n == 2 || pk >= maxpow) && !set.Contains(pk))
                    set.Add(pk);
            }
        }
        count += set.Count;
    }
    for (long n = sqrt; n < maxn; n++)
    {
        if (bit[(int)n])
            continue;
        count += maxpow - 3;
    }
    return count;
}

@sapbufer · 20.09.2016, 17:57 **[ТС]**

Shamil1, у меня в первом варианте также получилось, хотел себя перепроверить, решив по-другому,видимо в алгоритме проблемы. Спасибо!

@Shamil1 · 21.09.2016, 11:44

Сообщение от sapbufer

хотел себя перепроверить, решив по-другому

Обычно в таких случаях сначала пишут наиболее простое решение ("в лоб"). Например:

C#

long Test(long maxn, int maxpow)
{
    var set = new HashSet<long>();
    for (int n = 3; n < maxn; n++)
        for (int p = 3; p < maxpow; p++)
        {
            double pow = Math.Pow(n, p);
            if (pow > long.MaxValue) throw new OverflowException($"ERROR {pow}!!!");
            long np = (long)pow;
            if(!set.Contains(np))
                set.Add(np);
        }
    return set.Count;
}

А затем используют его для проверки своего оптимизированного решения на небольших входных данных (на больших обычно "решение в лоб" не работает из-за проблем с производительностью и т.п.).

@ProgJ · 21.09.2016, 16:20

Сообщение от Shamil1

Алгоритм вычисления k в GetK() меня немного смущает... но всё равно всё время уходит на разложение на множители

А я всё-таки попробовал подумать над GetK, но на скорости вычислений действительно не отражается
вот мой вариант

C#

        static int GetK(int p, int cnt)
        {
            List<int> pwrs = new List<int>();   //здесь степени p
            List<int> pwrsSum = new List<int>();    //здесь суммы степеней
 
            int s = 1;
            int pw = 1;
            while (s <= cnt)
            {
                pwrs.Add(pw);
                pwrsSum.Add(s);
                pw *= p;
                s += pw;
            }
 
            int k = 0;
            for(int i = pwrs.Count - 1; i >= 0; i--)
            {
                s = pwrsSum[i];
                int cntOld = cnt;
                cnt = cnt % s;
                k += (cntOld - cnt) / s * pwrs[i];
            }
            return k * p;
        }

@Shamil1 · 21.09.2016, 18:08

C#

            for(int i = pwrs.Count - 1; i >= 0; i--)
            {
                s = pwrsSum[i];
                int cntOld = cnt;
                cnt = cnt % s;
                k += (cntOld - cnt) / s * pwrs[i];
            }

Можно обойтись одним делением.

C#

    for (int i = pwrs.Count - 1; i >= 0; i--)
    {
        s = pwrsSum[i];
        int d = cnt / s;
        k += d * pwrs[i];
        cnt -= d*s;
    }

Добавлено через 22 минуты
И можно не использовать списки:

C#

static int GetK(int p, int cnt)
{
    int bn = 1;
    while (bn < cnt)
    {
        bn *= p;
    }
 
    int k = 0;
    while (bn >= 1)
    {
        int sn = (bn * p - 1) / (p - 1);
        int d = cnt / sn;
        k += d * bn;
        cnt -= d * sn;
        bn = bn / p;
    }
    
    return k * p;
}

(подставил формулу для суммы геометрической прогрессии)
(не тестировал)

@ProgJ · 21.09.2016, 19:11

Сообщение от Shamil1

Можно обойтись одним делением.

точно

Сообщение от Shamil1

И можно не использовать списки

хорошая идея. Только операций больше получается

@ProgJ 90 / 87 / 11 Регистрация: 20.11.2008 Сообщений: 724
	21.09.2016, 19:11	26
	Сообщение от Shamil1 Можно обойтись одним делением. точно Сообщение от Shamil1 И можно не использовать списки хорошая идея. Только операций больше получается 0

@sapbufer 0 / 0 / 0 Регистрация: 27.11.2014 Сообщений: 38
	20.09.2016, 17:57 [ТС]	22
	Shamil1, у меня в первом варианте также получилось, хотел себя перепроверить, решив по-другому,видимо в алгоритме проблемы. Спасибо! 0

Найти минимальное число, факториал которого будет делиться на определенное число

Решение