Вопросы с тегом «number-theory»

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

28
Проблема сумм подмножеств со многими условиями делимости

Пусть SSS множество натуральных чисел. Мы рассматриваем в частичном порядке делимости, т.е. . ПозволятьSSSs1≤s2⟺s1∣s2s1≤s2⟺s1∣s2s_1 \leq s_2 \iff s_1 \mid s_2 α(S)=max{|V|∣V⊆S,Vα(S)=max{|V|∣V⊆S,V\qquad \displaystyle \alpha(S) = \max \{|V| \mid V\subseteq S, V антицепь }}\} . Если мы рассмотрим...

23
Сложность прохождения мода

Это похоже на вопрос, который должен иметь простой ответ, но у меня нет однозначного ответа: Если у меня есть два битных числа , какова сложность вычисления ?nnna,pa,pa, pamodpamodpa\bmod p Простое деление aaa на ppp заняло бы время O(M(n))O(M(n))O(M(n)) где M(n)M(n)M(n) - сложность умножения. Но...

20
Как эффективно найти элемент последовательности Digit Sum?

Просто ради интереса я попытался решить проблему из категории «Недавние» Project Euler ( последовательность цифр суммы ). Но я не могу придумать, как решить проблему эффективно. Проблема заключается в следующем (в исходной последовательности вопросов в начале есть две, но она не меняет...

13
Алгоритмические следствия алгебраической формулы для функции разбиения?

Брюинье и Оно нашли алгебраическую формулу для функции разбиения , которая, как сообщалось, была прорывом. Я не могу понять статью, но имеет ли она какие-либо алгоритмические последствия для быстрого вычисления функции...

12
Как быстро мы можем найти все комбинации четырех квадратов, которые суммируются с N?

Вопрос был задан при переполнении стека ( здесь ): Принимая во внимание целое число , распечатать все возможные комбинации целочисленных значений и , которые решают уравнение .NNND A 2 + B 2 + C 2 + D 2 = NA , B , CA,B,CA,B,CDDDA2+ B2+ C2+ D2= NA2+B2+C2+D2=NA^2+B^2+C^2+D^2 = N Этот вопрос, конечно,...

12
Предположение Гольдбаха и численность занятого бобра?

Справочная информация: я полный дилетант в области компьютерных наук. Я читал о занятых номерах Бивер здесь , и я нашел следующий отрывок: Человечество может никогда не узнать значение BB (6) наверняка, не говоря уже о значении BB (7) или любом более высоком числе в последовательности. На самом...

11
Наименьший общий неделитель

В основном проблема заключается в следующем: для набора положительных чисел найти минимальное число , которое не является делителем ни одного элемента из , т. .SSSdddSSS∀x∈S, d∤x∀x∈S, d∤x\forall x \in S,\ d \nmid x Обозначим n=|S|n=|S|n = |S|и C=max(S)C=max(S)C = \max(S) . Рассмотрим функцию...

10
Нахождение размера наименьшего подмножества с GCD = 1

Это проблема с практической сессии Польского студенческого соревнования по программированию 2012 года . Хотя я мог найти решения для основного конкурса, я не могу найти решение этой проблемы где-либо. Проблема в том, что: учитывая набор из различных положительных целых чисел, не превышающих ,...

9
Эффективно найти максимальный попарно GCD из множества натуральных чисел

Рассмотрим следующую проблему: Пусть - конечное подмножество натуральных чисел.S= { с1, с2, . , , sN}Sзнак равно{s1,s2,,,,sN}S = \{ s_1, s_2, ... s_n \} Пусть | где - наибольший общий делитель и yg c d ( s i , s j ) s i , s j ∈ S , s i ≠ s j } g c d ( x , y ) x yG = {гзнак равно{G = \{ гс д( ся,...

9
Эффективное вычисление наименьшего целого числа с n делителями

Чтобы решить эту проблему, я сначала заметил, что ϕ(pe11 pe22⋯ pekk)=(e1+1)(e2+1)⋯(ek+1)ϕ(p1e1 p2e2⋯ pkek)=(e1+1)(e2+1)⋯(ek+1)\phi(p_1^{e_1} \space p_2^{e_2} \cdots \space p_k^{e_k}) = (e_1 + 1)(e_2 + 1)\cdots(e_k +1) Где ϕ(m)ϕ(m)\phi(m) - число (не обязательно простых) делителей числа mmm . Если...