Описание тега number-theory
Теория чисел - это раздел математики, который исследует свойства чисел, обычно целых.
2
ответа
Самый эффективный способ найти последнюю цифру a^b
Я новичок в питоне. Я ищу вычислить (a ** b) % 10 наиболее эффективным способом (то есть упрощение силовой части). Я нашел один способ сделать это: ((a % 10) ** b) % 10, У меня вопрос, есть ли более эффективные способы сделать это? Эта проблема явля…
08 июл '17 в 07:01
0
ответов
Python, работающий с большими числами, вызывает ошибки на полях
Приветствие ребят. Я выполнял алгоритм, предназначенный для получения числа разделов целого числа. Когда я тестировал свою программу, ошибки маржи начали появляться, когда n> 257. У меня фактически была та же самая проблема по другому вопросу, работ…
23 апр '18 в 12:46
3
ответа
Как я могу определить, можно ли составить определенное число из набора чисел?
Итак, у меня есть целое число, например, 1234567890, и заданный набор чисел, например, {4, 7, 18, 32, 57, 68}. Вопрос в том, можно ли составить 1234567890 из указанных чисел (вы можете использовать число более одного раза, и вам не нужно использоват…
22 дек '15 в 21:42
2
ответа
ACM ICPC - теория чисел
Я практиковал ACM ICPC в прошлом проблемы http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid;=8&page;=show_problem&problem;=1030 Я не могу решить эту проблему и совершенно не знаю, как сделать это эффективно в течение 3 секунд. Я дум…
07 апр '12 в 18:30
1
ответ
Система конгруэнций с непарными взаимно простыми модулями
У меня есть набор сравнений x = a1 (mod n) ... x = ak (mod nk) И я хочу найти xэто можно решить с помощью китайской теоремы об остатках и связанных с ней алгоритмов: https://en.wikipedia.org/wiki/Chinese_remainder_theorem Некоторые примеры: https://…
28 апр '18 в 21:48
2
ответа
n-е число, не являющееся числом Фибоначчи
Как найти n-е не-число Фибоначчи в o(logn)не-числа Фибоначчи: 4,6,7,9,10....Приведенная ниже функция дает не-число Фибоначчи для данного значения n static int nonFibonacci(int n){ int a=1,b=2,c=3; while(n>0){ a=b; b=c; c=a+b; n-=(a-1); } n+=(a-1)…
25 июл '15 в 14:42
1
ответ
Любопытное поведение обратного по модулю
Я написал следующий код для вычисления n! По модулю p... Учитывая, что n и p близки... но он работает довольно забавным образом, не могу выяснить ошибку.. Есть некоторое переполнение где-то.. Ограничения 1 1<= N <= 2*10^9, хотя в некоторых случаях о…
02 ноя '13 в 14:51
10
ответов
Получение списка свободных от квадратов чисел
Один из способов получить это для натуральных чисел (1,..,n), мы разложим их по частям и посмотрим, есть ли у них повторяющиеся простые множители, но для больших n это займет много времени. Так есть ли лучший способ получить числа без квадратов от 1…
15 мар '11 в 14:32
7
ответов
Алгоритм определения существования решения с неотрицательными значениями для линейного диофантового уравнения
Я ищу метод, чтобы определить, есть ли решение для уравнений, таких как:3n1 + 4n2 + 5n3 = 456, где n1,n2,n3 являются положительными целыми числами. Или более общий: существуют ли нулевые или положительные целые числа n1,n2,n3..., которые решают урав…
23 сен '09 в 18:46
3
ответа
Расчет 1^X + 2^X + ... + N^X мод 1000000007
Есть ли алгоритм для расчета (1^x + 2^x + 3^x + ... + n^x) mod 1000000007? Замечания: a^b является b-й степенью а. Ограничения 1 <= n <= 10^16, 1 <= x <= 1000, Таким образом, значение N очень велико. Я могу решить только за O(m log m) ес…
17 янв '17 в 10:56
1
ответ
Вычислить x ^ (1 / y) mod m fast (модульный корень)
Как быстро решить x ^ ( 1 / y) mod m, где x, y, m - все положительные целые числа? Это обратный расчет для x ^ y mod m. Например сторона A вручает стороне B заранее согласовать положительное целое число y и m сторона A генерирует число x1 (0 партия …
08 апр '18 в 07:52
1
ответ
Как создать открытый ключ для криптосистемы Okamoto Uchiyama?
Я внедряю криптосистему Окамото Утияма в Java. Алгоритм здесь Для открытого ключа значение параметра h рассчитывается как h = g^n mod n где, g является корнем простого числа p (340 битов) n = p^2 * q (1024bits) Я использовал тип BigInteger для g, h …
04 янв '15 в 10:41
1
ответ
Хэш-функция MASH-2
Мы взяли хэш-функцию MASH-2 в курсе колледжа, и на экзамене мы сталкиваемся с вопросами, чтобы вычислить что-то вроде этого ((62500)^257)) мод (238194151), используя только научный калькулятор. теперь я знаю некоторые теории с a^b (mod n), но пробле…
19 июл '12 в 09:54
0
ответов
Головоломка Monk и Divisor Hackerearth (вычисление количества элементов в массиве, делимого на конкретные числа)
Я решил эту проблему и решил ее с помощью% операции, но это отнимает много времени, и мое решение было принято только частично. Эффективное по времени решение - это то, чего я не мог понять. Точнее, есть конкретная часть решения, которую я не мог по…
26 авг '18 в 09:22
3
ответа
Генератор псевдослучайных чисел с небольшим смещением
Я думал об этом некоторое время безрезультатно... Как можно было бы создать генератор псевдослучайных чисел с небольшим (мы говорим только очевидным после миллионов, может быть, миллиардов итераций / тестов) смещением в сторону одного числа. Так, на…
17 янв '18 в 05:19
4
ответа
Быстрый алгоритм минимизации псевдодиофантова уравнения
Мы ищем алгоритм для решения этой проблемы в O(N). по двум действительным числам a и b (без ограничения общности можно предположить, что они оба находятся между 0 и 1). Найдите целое число n между -N и N, которое минимизирует выражение: | an - b - р…
25 янв '12 в 22:20
0
ответов
Увеличьте точность в PARI/GP с помощью bnfinit
Есть ли способ повысить точность еще больше в PARI/GP, если флаг =2 должен увеличивать точность до тех пор, пока не будет вычислен альфа (второй вектор)? Сколько памяти это потребует? Я настаиваю на вычислении главных генераторов. Конкретная ошибка,…
07 янв '18 в 06:23
0
ответов
Как решить алицею на спой. Как у него есть общий образец для его ответа
Какова логика, лежащая в основе паттерна, т.е.(ans=(n+1)/2) в вопросе ALICESIE о спой. Algorithm_given: 1.Создайте список последовательных целых чисел от N до 2 (N, N-1, N-2, ..., 3, 2). Все эти номера N-1 изначально не отмечены.2. Вначале пусть P б…
01 июл '18 в 00:09
7
ответов
Создайте более быструю функцию Фибоначчи для n > 100 в MATLAB / октава
У меня есть функция, которая сообщает мне n-е число в последовательности Фибоначчи. Проблема в том, что он становится очень медленным при попытке найти большие числа в последовательности Фибоначчи, кто-нибудь знает, как я могу это исправить? functio…
09 ноя '14 в 14:24
1
ответ
Как я могу получить элементы антицепи в SPOJ-DIVREL?
Проблема: http://www.spoj.com/problems/DIVREL В вопросе нам просто нужно найти максимальное количество элементов, которые не кратны (делится на форму b) из заданного набора элементов. Если мы просто сделаем ребро от элемента до его кратного и постро…
25 май '14 в 18:23