Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Интересные и занимательные задачи по программированию > Найти минимальное число

Автор: Akina 14.12.2007, 21:28

Дано N пар целых чисел Ai,Bi, причем Ai>Bi и нет равных Ai,Aj.
Найти минимальное M, которое при делении на Ai даст в остатке Bi.

Или в олимпиадной трактовке:

Входной файл: в первой строке целое N>1, далее в N строках пары целых Ai,Bi, причем Ai>Bi и нет равных Ai,Aj.
Выходной файл: минимальное положительное M, которое при делении на любое из данных Ai даст в остатке Bi.

Пример:

Входной файл
3
3 1
4 2
7 2

Выходной файл
58

Примечания:
1) Хоть среди чисел Ai нет равных, это не значит, что все они взаимно просты...
2) Некоторые Bi могут быть равны нулю

Само собой, достаточно описать алгоритм поиска такого M. Плюс алгоритм обнаружения, что входные данные противоречивы.

Автор: stab 15.12.2007, 18:59

в общем, у меня вот так получилось:

Код


class Program
{
    static void Main(string[] args)
    {
        var sortedByGrowthSpeed = InputPairs.OrderByDescending(pair => pair.A);
        var fastestGrowing = sortedByGrowthSpeed.First();
        var slowlyGrowingPairs = sortedByGrowthSpeed.Skip(1).ToArray();

        var start = slowlyGrowingPairs.All(pair => pair.B == 0) ? 1u : 0u;
        var maxIterations = slowlyGrowingPairs.Aggregate(1u, (total, pair) => total * pair.A);

        var m = 0u;
        var found = false;
        for (var k = start; k <= maxIterations; k++)
        {
            m = (fastestGrowing.A * k) + fastestGrowing.B;
            found = true;
            foreach (var pair in slowlyGrowingPairs)
            {
                if ((m % pair.A) != pair.B)
                {
                    found = false;
                    break;
                }
            }
            if (found)
            {
                break;
            }
        }

        if (found)
        {
            Console.WriteLine("Dear sir, my congratulations, I have found the M = {0}.", m);
        }
        else
        {
            Console.WriteLine("Dear sir, my apologise, there is no solution.");
        }

        Console.ReadLine();
    }

    static readonly InputPair[] InputPairs = new InputPair[]
    {
        new InputPair(3, 1),
        new InputPair(4, 2),
        new InputPair(7, 2)
    };

    struct InputPair
    {
        public InputPair(uint a, uint b)
        {
            A = a;
            B = b;
        }

        public uint A;
        public uint B;
    }
}

наверное, можно как-то умнее, но тогда, видимо, придётся заниматься факторизацией, что тоже трудоёмко и неизвестно отобьёт ли свои затраты.

Автор: Akina 15.12.2007, 22:23

Перебор - не решение. Пусть и с самым большим возможным шагом. А есмли пойдет речь о работе в сверхдлинных числах? Программа не отработает до конца, потому что комп в пыль рассыплется от старости.

Добавлено через 8 минут и 14 секунд
Сосбственно суть задачи - именно в поиске зависимостей, способных уйти от перебора или значимо его оптимизировать.

Автор: stab 16.12.2007, 05:34

для Bi-ых равных нулю, искомое есть произведение простых чисел в наибольшей степени полученных после факторизации всех Ai. по-идее, это можно адаптировать и под ненулевые Bi. перебора нет, но для сверхбольших чисел факторизация - та ещё задачка и от перебора не особо отличается. ничего другого в голову не приходит.

Автор: stab 16.12.2007, 09:27

.. оО! кое-что пришло в голову! ща буду проверять, не говори решение. smile

Автор: Akina 16.12.2007, 23:37

Цитата(stab @ 16.12.2007, 10:27

)

ща буду проверять, не говори решение

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

Автор: SelenIT 17.12.2007, 08:27

Цитата(Akina @ 15.12.2007, 22:23

)

или значимо его оптимизировать.

Есть вот такая наивная идея: группируем все Ai для каждого из различных Bj. (M - Bj) должно делиться на НОК Ai соответствующей группы (в примере, M-2 должно делиться на 28). Находим среди всех НОК групп наибольшее и пробуем числа-кандидаты с таким шагом, проверяя, выполнятся ли для него остальные условия (делится ли оно на НОК других групп с требуемым остатком). Номера шагов, кратные хотя бы одному из чисел Ai, вошедших в другие группы, очевидно, пропускаем. Также очевидно, что если в какой-то группе хотя бы одно число Ai кратно другому, то достаточно пропускать шаги, кратные минимальному из них.

Если какое-то из чисел Ai кратно числу Aj из другой группы - входные данные противоречивы (пример - пары входных чисел 4, 2 и 8, 5).

Для приведенного примера: явного признака противоречивости данных нет, есть две группы по остатку. В группе с остатком 1 - 1 число, НОК=3; группа с остатком 2 - 2 числа, НОК = 28. Следовательно, шаг перебора = 28.
Первый кандидат = 28*1+2 = 30. Проверяем, остаток от деления на 3 равен 0, а не 1 - не подходит.
Второй кандидат = 28*2+2 = 58. Проверяем, остаток от деления на 3 равен 1. Ответ найден.

Если бы второй кандидат не подошел, то проверять третьего кандидата не имело бы смысла, т.к. 28*3+2 автоматически не может делиться на 3 с единицей в остатке. Проверять числа, бОльшие, чем НОК всех Ai, имхо тоже нет смысла, потому что ситуация с остатками полностью повторяется с такой периодичностью. Так что достижение этого порога - второй критерий противоречивости входных данных.

Можно ли считать это существенной оптимизацией перебора?

Автор: stab 17.12.2007, 09:52

Цитата(Akina @ 17.12.2007, 03:37

)

на полусотне входных пар.

выдай их, плиз, чтобы на одних данных тестировали.

Автор: Akina 17.12.2007, 10:02

Цитата(SelenIT @ 17.12.2007, 09:27

)

Можно ли считать это существенной оптимизацией перебора?

Это пока одна из двух оптимизаций, давшая существенный эффект. Вторая - разделение Ai на простые делители Aij для каждого Ai,Bi и просчет соотв. Bij. Заодно именно в этот момент происходит проверка валидности входных данных. Построение сетки остатков на пространстве НОД хотя и обещало изрядное ускорение, но на практике для НЕ взаимно простых Ai,Aj оказалось излишне вычислительноемким.

Цитата(stab @ 17.12.2007, 10:52

)

выдай их, плиз, чтобы на одних данных тестировали.

Реальные данные имеют приблизительно следующие ограничения:
10<N<1000
100<A<1000000
0<B<A/2

Так что вполне можно тестировать скорость на, скажем

Код


for i=1 to 100
  A(i)=Random(10,1000)
  B(i)=Random(0,A(i)/2)
next i

Однако результат гарантированно вылетает за int64...

Автор: stab 17.12.2007, 16:13

фуф, ну кажися сделал:

Код


class Program
{
    static void Main(string[] args)
    {
        //GenerateRandomInput();
        //PrintInputValues();

        Console.WriteLine("Intersecting partial solutions...");
        bool noSolution = false;
        Pair intersection = new Pair();

        DiophantineSolution solution = SolveDiophantineEquation(
            InputPairs[0].A, -InputPairs[1].A,
            InputPairs[1].B - InputPairs[0].B);

        if (solution.HasSolution)
        {
            intersection = new Pair(
                InputPairs[0].A * InputPairs[1].A / solution.Gcd,
                InputPairs[0].A * solution.X0 + InputPairs[0].B);
            Console.WriteLine(intersection);

            for (int i = 1; i < InputPairs.Length; i++)
            {
                solution = SolveDiophantineEquation(
                    intersection.A, -InputPairs[i].A,
                    InputPairs[i].B - intersection.B);

                if (!solution.HasSolution)
                {
                    noSolution = true;
                    break;
                }

                intersection = new Pair(
                    intersection.A * InputPairs[i].A / solution.Gcd,
                    intersection.A * solution.X0 + intersection.B);
                Console.WriteLine(intersection);
            }
        }
        else
        {
            noSolution = true;
        }


        if (noSolution)
        {
            Console.WriteLine("\nDear sir, my apologise, there is no solution.");
        }
        else
        {
            int m = intersection.GetValue(intersection.B == 0 ? 1 : 0);
            Console.WriteLine("\nDear sir, my congratulations, I have found the M = {0}.", m);
        }

        Console.ReadLine();
    }

    static Pair[] InputPairs = new Pair[]
    {
        new Pair(3, 1),
        new Pair(4, 2),
        new Pair(7, 2),
        //new Pair(15, 10),
        //new Pair(101, 5)
    };

    static void PrintInputValues()
    {
        Console.WriteLine("Input pairs: ");
        for (int i = 0; i < InputPairs.Length; i++)
        {
            Console.WriteLine(InputPairs[i]);
        }
        Console.WriteLine();
    }

    static void GenerateRandomInput()
    {
        Random random = new Random();
        InputPairs = new Pair[2 + random.Next(1000)];
        for (int i = 0; i < InputPairs.Length; i++)
        {
            InputPairs[i].A = 1 + random.Next(1000);
            InputPairs[i].B = random.Next(InputPairs[i].A / 2);
        }
    }

    struct Pair
    {
        public Pair(int a, int b)
        {
            A = a;

            if (Math.Abs(b) >= a)
            {
                b %= a;
            }

            if (b >= 0)
            {
                B = b;
            }
            else
            {
                B = a + b;
            }
        }

        public int A;
        public int B;

        public override string ToString()
        {
            return A.ToString() + " * t + " + B.ToString();
        }

        public int GetValue(int t)
        {
            return A * t + B;
        }
    }

    static DiophantineSolution SolveDiophantineEquation(int a, int b, int c)
    {
        GcdExtResult gcdResult = GcdExt(a, b);
        if (gcdResult.Gcd != 0 && c % gcdResult.Gcd == 0)
        {
            c /= gcdResult.Gcd;
            return new DiophantineSolution(true, gcdResult.U * c, gcdResult.V * c,
                gcdResult.Gcd);
        }
        else
        {
            return new DiophantineSolution(false, 0, 0, 0);
        }
    }

    struct DiophantineSolution
    {
        public DiophantineSolution(bool hasSolution, int x0, int y0, int gcd)
        {
            HasSolution = hasSolution;
            X0 = x0;
            Y0 = y0;
            Gcd = gcd;
        }

        public bool HasSolution;
        public int X0;
        public int Y0;
        public int Gcd;

        public override string ToString()
        {
            return string.Format("{0}, {1}, {2}", HasSolution, X0, Y0);
        }
    }

    static GcdExtResult GcdExt(int a, int b)
    {
        int x1 = 0;
        int y1 = 0;
        int x2 = 0;
        int y2 = 0;
        int x3 = 0;
        int y3 = 0;
        int q = 0;
        int r = 0;
        int sa = 0;
        int sb = 0;

        if (b != 0 & a != 0)
        {
            x2 = 1;
            x1 = 0;
            y2 = 0;
            y1 = 1;
            sa = Math.Sign(a);
            sb = Math.Sign(b);
            a = Math.Abs(a);
            b = Math.Abs(b);
            while (b > 0)
            {
                q = a / b;
                r = a - q * b;
                x3 = x2 - q * x1;
                y3 = y2 - q * y1;
                a = b;
                b = r;
                x2 = x1;
                x1 = x3;
                y2 = y1;
                y1 = y3;
            }
            return new GcdExtResult(a, sa * x2, sb * y2);
        }
        else
        {
            return new GcdExtResult(0, 0, 0);
        }
    }

    struct GcdExtResult
    {
        public GcdExtResult(int gcd, int u, int v)
        {
            Gcd = gcd;
            U = u;
            V = v;
        }

        public int Gcd;
        public int U;
        public int V;

        public override string ToString()
        {
            return string.Format("{0}, {1}, {2}", Gcd, U, V);
        }
    }
}

вкратце, идея такова, происходит решение линейных диафантовых уравнений с двумя неизвестными, т.е. решение аналитическое. каждое решение позволяет создать пересечение решений уже решённых уравнений и очередной пары, и в итоге это приводит (или не приводит при отсутствии решений\пересечений) к одной паре At + B, M = B при t = 0, или при B равном 0, М = А, что требуется по условию задачи. трудоёмкость алгоритма, как можно заметить, пропорциональна N, но оптимизировать ещё много куда есть. smile

спасибо, хорошая задачка. основательно подучил теорию чисел, за два дня с нуля. smile

Автор: Akina 17.12.2007, 16:26

Цитата(stab @ 17.12.2007, 17:13

)

вкратце, идея такова

Теперь осталось мне, с моим практически нулевым знанием Си, во всем этом разобраться... но это уже чисто технический вопрос.

Автор: stab 17.12.2007, 16:29

это C#, он попроще немного. smile

Автор: stab 17.12.2007, 17:29

.. поподробнее. нужно решить систему уравнений в целых числах:

A1 * X1 + B1 = M
A2 * X2 + B2 = M
..
Ai * Xi + Bi = M

неизвестные: Xi и М. система недопределена, поэтому решений, если таковые имеются, множество. как это водится для таких систем будем решать следующим образом, избавимся от M:

A1 * X1 + B1 = A2 * X2 + B2

замечаем, что это обычное линейное диафантово уравнение с двумя неизвестными:

A1 * X1 - A2 * X2 = B2 - B1

его решения выражаются, в данном случае, как:

X1 = Z1 + A2 * t
X2 = Z2 + A1 * t

Z1 = (B2 - B1) * U и Z2 = (B2 - B1) * V, U и V - коэффициенты Безу. самое замечательное, что после решения этого уравнения X1 и X2 выражаются через одну переменную t, подставив в исходное уравнение получаем:

A1 * (Z1 + A2 * t) + B1 = A2 * (Z2 + A1 * t) + B2
A1 * A2 * t + A1 * Z1 + B1 = A1 * A2 * t + A2 * Z2 + B2 - что является верным тождеством.

выходит, что уравнение с двумя неизвестными мы свели к одному с одним неизвестным t и теперь вправе воспользоваться одной из частей тождества. дальше всё просто:

A1 * A2 * t + A1 * Z1 + B1 = A3 * X3 + B3

решаем тем же способом, выражаем через одну переменную, и так далее в том же духе для всех Ai * Xi + Bi. при подстановке реальных чисел главное не забывать сокращать коэффициент при t на наибольший общий делитель, полученный при вычислении U и V, и приводить данные к нормализованному виду - при необходимости, A1 * Z1 + B1 делить по модулю на A1 * A2 и выражать в положительных числах по тому же модулю.

в итоге, получается одно уравнение-решение всей системы, которое является пересечением всех индивидуальных решений исходных уравнений в исходной системе:

AF * t + BF = M

т.к. мы решаем в целых числах и BF < AF и AF > 0 (из природы данных), то M = AF * 0 + BF = BF или M = AF * 1 при BF = 0.