|
Доброго времени суток! Мы по очереди проверяем, попадает ли хотя бы один корень из данной пары в указанный отрезок, если нет - прекращаем проверки. (Мой вариант: если $%(\space [floor((Up-x_i)/p-(Down-x_i)/p) \ne0]\space OR \space[floor((Up-y_i)/p-(Down-y_i)/p) \ne 0]\space)$%, то попадает. задан 11 Авг '13 20:32 
miramentis |
|
Любой из алгоритмов (формул), предложенных выше (в описании задачи, ответе @falcao и коментариях к нему) будет работать в разы быстрее, чем само вычисление корней сравнения, если использовать операцию целочисленного деления вместо дробного с последующим округлением вниз. Не знаю, в паком мат. пакете или на каком языке Вы производите вычисления, но такое там обязательно есть. Так что по этому поводу можно не беспокоиться. отвечен 24 Авг '13 18:08 
chameleon |
|
Для упрощённого случая, когда имеется одна арифметическая прогрессия вида $%a+np$%, я бы поступил так. Сначала находим наибольшее целое $%n$%, для которого $%a+np\le u$%. Это не что иное как число $%n=\lfloor\frac{u-a}{p}\rfloor$%. Далее проверяем, верны ли неравенства $%n\ge1$% и $%d\le a+np$%. Если оба они верны, то одно из чисел прогрессии попадает в отрезок $%[d;u]$%; верно и обратное. К этому случаю, по идее, всё сводится, но если прогрессий много, то возможно, скорее всего, какое-то упрощение, чтобы не проверять всё подряд. Но тут желательно иметь какую-то дополнительную информацию. отвечен 12 Авг '13 21:03 
falcao Я правильно понимаю, что речь идёт об одном и том же квадратичном сравнении по модулю степеней одного и того же простого числа? Насколько велика при этом длина отрезка $%[d;u]$%? Если она не слишком большая, то можно проверить эти числа поочерёдно. Если же это долго, можно найти наибольшее $%k$%, для которого $%p^k$% попадает в отрезок, а потом применять метод половинного деления. То есть брать показатель примерно $%k/2$%, если $%k$% не годится, а потом искать показатель между $%0$% и $%k/2$%, или между $%k/2$% и $%k$% -- в зависимости от исхода.
(12 Авг '13 22:47)
falcao
вы все правильно понимаете.
(13 Авг '13 1:31)
miramentis
я вообще хотел конкретизировать задачу и поставил вопрос - что у меня не получается
(13 Авг '13 14:50)
miramentis
Я так понимаю, что проверка попадания числа в отрезок для данного фиксированного показателя степени не составляет труда и делается при помощи нахождения целой части. И тогда можно не проверять по отдельности каждое число $%i$%, воспользовавшись методом половинного деления. Чем не годится такой алгоритм? Он слишком медленный получается?
(13 Авг '13 15:17)
falcao
дело в том, что корней сравнения изначально нет. мы решаем сравнения до тех пор, пока хотя бы один корень попадает в отрезок. и начинаем с первой степени простого числа. как только это условие не выполняется - прекращаем
(13 Авг '13 21:18)
miramentis
1
А что если сделать так: взять алгоритм решения квадратичного сравнения из Вашего предыдущего вопроса, и применить его к нахождению корней из заданного отрезка. Тогда сначала решаем сравнение по модулю $%p$% и находим серии вида $%\pm x_0+pk$%, где $%k$% целое. Записываем неравенства вида $%d\le\pm x_0+pk\le u$%, после чего получаются границы для $%k$%. При этом длина отрезка $%[d;u]$% уменьшается примерно в $%p$% раз. Далее решаем сравнение по модулю $%p^2$%, где всё сводится к линейному сравнению по модулю $%p$% после подстановки. То есть этот алгоритм должен работать быстро.
(13 Авг '13 23:26)
falcao
да, отличный вариант. спасибо большое за ответ!
(21 Авг '13 11:35)
miramentis
показано 5 из 7
показать еще 2
|
У Вас в условии существенно, что $%n$% -- именно натуральное число? Или любое целое тоже бы подошло?
В том условии, которое Вы выписали в конце, фигурируют два числа, и между ними -- логическая связка "или". Там, наверное, какие-то неравенства имелись в виду, или я что-то не разобрал?
именно натуральные числа.
да, там следующим образом: либо левая скобка не ноль, либо правая не ноль. ну или обе не ноль. поправил еще: добавил округление вниз.