Задача состоит в следующем:
Имеются входные данные, выражения в форме (P)/D,
где P – полином с целыми коэффициентами и сумма выражений Cn^E;
D – положительный целый знаменатель.
Например список выражений:
(n^2-n)/2
(-n^14-11n+1)/3
....
и т.д.
Необходимо определить будет ли для любого положительного n результат выражения всегда целым числом.
т.е. при всех ли целых положительных n результат выражения будет целым числом или есть значения n
при которых выражение выдаёт дробный результат ?
_>Необходимо определить будет ли для любого положительного n результат выражения всегда целым числом. _>т.е. при всех ли целых положительных n результат выражения будет целым числом или есть значения n _>при которых выражение выдаёт дробный результат ?
представить полином в виде (n-t1)*(n-t2)...
где t1, t2 ... положительные коэфициенты.
убедиться что среди них есть непрерывная последовательность длинны D
Здравствуйте, eddy_cs, Вы писали:
_>(n^2-n)/2 _>(-n^14-11n+1)/3
_>Необходимо определить будет ли для любого положительного n результат выражения всегда целым числом. _>т.е. при всех ли целых положительных n результат выражения будет целым числом или есть значения n _>при которых выражение выдаёт дробный результат ?
По условию задачи P(n) делится на D, а также P(n+1) делится на D.
Отсюда следует, что P() делится на D, тогда и только тогда, когда:
1. P(0) делится на D, т.е. свободный член многочлена делится на D.
2. Многочлен P'() = P(n+1)-P(n) тоже делится на D.
Получили исходную задачу (п.2), но с многочленом P', который имеет степень на единицу меньше, чем исходный многочлен.
Выполнив несколько шагов мы уменьшим степень многочлена до нуля и сможем получить ответ. Вычисление многочлена P(n+1) — это вычисление биномиальных коэффициентов.
Пример (из задачи выше):
P = n^2-n
P' = P(n+1)-P(n) = (n^2+2n+1-n-1) — (n^2-n) = 2n
P'' = P'(n+1)-P'(n) = (2n+2)-2n = 2, т.е. делится на 2
Пример (из задачи выше):
P = -n^14-11n+1
свободный член = 1, не делится на D, значит найдутся n, при которых P(n) не делится на 3
Сложность такого алгоритма O(K^2), где K — степень многочлена.
Если D < K, то быстрее будет, как предложено в сообщении выше, рассчитать все значения P(n) по модулю D, где n = 0..D-1. Сложность O(K*D), где K — степень многочлена.
_>Необходимо определить будет ли для любого положительного n результат выражения всегда целым числом. _>т.е. при всех ли целых положительных n результат выражения будет целым числом или есть значения n _>при которых выражение выдаёт дробный результат ?
Насколько я понимаю, нужно получить коэффициенты Ai приведенной там формулы, и убедиться, что они целые.
Для больших степеней, пожалуй, накладно будет...
Здравствуйте, unreg_flex, Вы писали:
_>Возьмем n^2+1
согласен. лох.
... << RSDN@Home 1.2.0 alpha 4 rev. 1227>>
Re[2]: Расчет полинома
От:
Аноним
Дата:
28.04.10 19:27
Оценка:
Б>Если D < K, то быстрее будет, как предложено в сообщении выше, рассчитать все значения P(n) по модулю D, где n = 0..D-1. Сложность O(K*D), где K — степень многочлена.
Рассматриваем задачу P(n) = 0(mod D), P(n) степени К
если D — простое то D <= K.
И многочлен должен быть вида Y(n) * n(n-1)*..(n-d+1). потому что в поле нет делителей нуля.
Если D — составное, то тогда может быть и меньшей степени.
Re[3]: Расчет полинома
От:
Аноним
Дата:
28.04.10 19:33
Оценка:
Здравствуйте, unreg_flex, Вы писали:
_>Здравствуйте, cvetkov, Вы писали:
C>>представить полином в виде (n-t1)*(n-t2)... C>>где t1, t2 ... положительные коэфициенты.
_>Возьмем n^2+1 _>представляйте ...
Надо добавить в кольце вычетов D.
тогда если D = 2 то
n^2+1 = (n+1)*(n+1)
Здравствуйте, Буравчик, Вы писали:
Б>По условию задачи P(n) делится на D, а также P(n+1) делится на D.
Б>Отсюда следует, что P() делится на D, тогда и только тогда, когда: Б>1. P(0) делится на D, т.е. свободный член многочлена делится на D. Б>2. Многочлен P'() = P(n+1)-P(n) тоже делится на D.
Б>Получили исходную задачу (п.2), но с многочленом P', который имеет степень на единицу меньше, чем исходный многочлен. Б>Выполнив несколько шагов мы уменьшим степень многочлена до нуля и сможем получить ответ. Вычисление многочлена P(n+1) — это вычисление биномиальных коэффициентов.
Б>Пример (из задачи выше): Б>P = n^2-n Б>P' = P(n+1)-P(n) = (n^2+2n+1-n-1) — (n^2-n) = 2n Б>P'' = P'(n+1)-P'(n) = (2n+2)-2n = 2, т.е. делится на 2
Б>Пример (из задачи выше): Б>P = -n^14-11n+1 Б>свободный член = 1, не делится на D, значит найдутся n, при которых P(n) не делится на 3
Б>Сложность такого алгоритма O(K^2), где K — степень многочлена.
Б>Если D < K, то быстрее будет, как предложено в сообщении выше, рассчитать все значения P(n) по модулю D, где n = 0..D-1. Сложность O(K*D), где K — степень многочлена.
Спасибо Вам за подробный ответ.
Но как поступить если степень велика ? Степень максимально может иметь значение — 100
Здравствуйте, Буравчик, Вы писали:
Б>А ограничения на D какие?
D может изменятся от 1 до 2^31
Совершенно согласен с Вами, что когда D мало, подставить значения n (в диапазоне от 0 до D-1) во входное выражение, будет приемлемым решением.
Но когда D будет ближе к 2^31, необходимо немного другое решение.
В программе предполагается оценить выражение, если D имеет небольшое значение
идем по 1-му варианту решения (как Вы предложили подставить в полином n в диапазоне от 0 до D-1),
иначе (если D большое) идем по 2-варианту решения (???)
Пороговое значение, с которым проверяется D, хранится в конфигурации программы.
_>D может изменятся от 1 до 2^31 >>Степень максимально может иметь значение — 100
Если D простое,то степень К не может быть меньше D для удовлетворения условиям.
Если D составное, то степень не может быть меньше phi(D) (функция эйлера — количество взаимно простых с D и <D).
(Это гипотеза но интуитивно где-то здесь), так как взаимно простые с D не являются делителями нуля.
Поэтому ограничения на D здесь не особо важны. для больших D автоматом будет fail.
график phi(D) http://ru.wikipedia.org/wiki/Файл:EulerPhi.svg
При K <= 100 верхняя граница по D будет {phi(D) <= 100}. ну явно MaxD << 1000.
Всё решается грубой проверкой порядков K и phi(D).
1) false при слишком больших D
2) подстановкой чисел от (0 до D-1) по модулю D.
Re[6]: Расчет полинома
От:
Аноним
Дата:
30.04.10 18:24
Оценка:
Вот ещё алгоритм:
1) сокращаем НОД(коэфф) и приводим коэфф по модулю D
2) Если D — простое то заменяем n^D на n пока возможно,
получился 0 => true
иначе => false
/n^D — n = 0 (mod D) для любого n по т. Эйлера. и по т.Безу разложение по корням над полем будет n(n-1)(n-2).. и
многочлены одной степени над полем совпадают, если все корни совпадают/
3) Если D = степень простого, — то
одна надежда, что K действительно должно быть >= phi(D) (как доказать не знаю). и проверять подстановкой.
4) Если D = разложению в простые, то для каждого элемента из разложения пункт 2 или 3 должен быть истинным.
Re[2]: Расчет полинома
От:
Аноним
Дата:
02.05.10 21:57
Оценка:
Здравствуйте, Буравчик, Вы писали: Б>Отсюда следует, что P() делится на D, тогда и только тогда, когда: Б>1. P(0) делится на D, т.е. свободный член многочлена делится на D. Б>2. Многочлен P'() = P(n+1)-P(n) тоже делится на D.
и т.д.
Вобщем вы не знаете случайно зачем тут коэффициенты многочленов считать?
Согласно приведённой схеме мы знаем, что надо сделать не более К + 1 проверок, после этого у нас должен получится многочлен 0 степени.
ну значит и проверяем F от 0 до K ?
Здравствуйте, Аноним, Вы писали:
А>Если D простое,то степень К не может быть меньше D для удовлетворения условиям. А>Если D составное, то степень не может быть меньше phi(D) (функция эйлера — количество взаимно простых с D и <D). А>(Это гипотеза но интуитивно где-то здесь), так как взаимно простые с D не являются делителями нуля.
А>Поэтому ограничения на D здесь не особо важны. для больших D автоматом будет fail. А>график phi(D) http://ru.wikipedia.org/wiki/Файл:EulerPhi.svg
А>При K <= 100 верхняя граница по D будет {phi(D) <= 100}. ну явно MaxD << 1000.
А>Всё решается грубой проверкой порядков K и phi(D). А>1) false при слишком больших D А>2) .
Не понятно как можно реализовать phi(D) в программе.
Т.е. считаем если D > 1000, значит будут значения n при которых полином выдаёт дробный результат
Если D < 1000, значит подставляем n от (0 до D-1) в полином и анализируем получился ли на этом диапазоне дробный результат
??
Re[7]: Расчет полинома
От:
Аноним
Дата:
05.05.10 17:28
Оценка:
_>Не понятно как можно реализовать phi(D) в программе. _>Т.е. считаем если D > 1000, значит будут значения n при которых полином выдаёт дробный результат _>Если D < 1000, значит подставляем n от (0 до D-1) в полином и анализируем получился ли на этом диапазоне дробный результат _>??
это я не в ту степь.
про phi это просто гипотеза была о том как примерно устроены такие многочлены. не обращайте внимания.
Помоему для вашей задачи чисто практически достаточно уже приведённого решения =
проверить F в точках [0.. min(K, D-1)] по модулю D.
Если хочется поразнообразней, то можно факторизовать D чтоб получить разложение в простые, но это уже само по себе может быть достаточно громоздким.
И тогда тут уже можно воспользоваться простой проверкой коэффициентов многочлена для каждого простого числа из разложения.
При этом для степеней простых в разложении мне так и непонятна хорошая формула. так что для них всё равно вычислять F в диапазоне придётся.
