Вопросы с меткой [теория-чисел]

Теория чисел (в узком смысле) занимается свойствами целых чисел: делимостью (простые числа, НОД/НОК, сравнения по модулю), решением уравнений в целых числах (диофантовы уравнения, пифагоровы тройки). К ней же относятся цепные дроби, числа Фибоначчи (и многие другие числа с именами), большая и малая теоремы Ферма и многое, многое другое.

Фильтрация
Сортировка
Метки
7 голосов
3 ответа
263 показа

Программа для поиска приветливых чисел

Назовём натуральное число приветливым, если для любого натурального n⩾2 энная цифра этого числа равна остатку этого числа при делении на n . Например, число 2123 является приветливым, так как даёт ...
Ян Альбертович Дененберг's user avatar
0 голосов
1 ответ
76 показов

Алгоритм нахождения всех делителей большого числа

Мне попалась задача, суть такова: сложить делители числа n и сравнить сумму с самим n. Но вопрос не про это - вопрос в том, чтобы найти эти делители для огромных чисел, например, для 23_459_879_034. ...
Emil Gerz's user avatar
0 голосов
1 ответ
347 показов

Алгоритм перебора чисел

Назовём нетривиальным делителем натурального числа его делитель, не равный единице и самому числу. Например, у числа 6 есть два нетривиальных делителя: 2 и 3. Найдите все натуральные числа, ...
Marilyn Manson's user avatar
0 голосов
3 ответа
708 показов

Найдите пять наименьших значений k, при которых N(k) имеет нечётное количество различных чётных делителей

Пусть N(k) = 1 850 000 000 + k, где k – натуральное число. Найдите пять наименьших значений k, при которых N(k) имеет нечётное количество различных чётных делителей. В ответе запишите найденные ...
daniil's user avatar
  • 13
1 голос
1 ответ
100 показов

возможно ли из a получить b

всем привет, есть два числа, нужно проверить возможно ли получить из числа a другое число b, умножая его на число которое делится на a и посчитать кол-во шагов за которое это можно сделать, например: ...
ch1ba's user avatar
  • 53
0 голосов
1 ответ
83 показа

Задача на gcd, не понятна логика условия

В начале игры у вас есть массив a длины n. За один ход можно выбрать два соседних элемента и заменить один из них на наибольший общий делитель этих двух чисел. То есть из двух соседних чисел x и y ...
Диана's user avatar
-2 голоса
2 ответа
128 показов

Задача на автоморфные числа. Язык Си

Автоморфными называются числа, которые содержатся в последних разрядах их квадрата, например, десятичные числа: 52 = 25, 252 = 625. Автоморфные числа существуют в системе счисления, основание n ...
Myth Math's user avatar
0 голосов
2 ответа
111 показов

Алгоритм сам завершается(хотя должен продолжаться)

Условие: Алгоритм принадлежит числовому отрезку [A;B] (1<A<B<1000000) выводит числа,имеющие среди делителей ровно три различных натуральных нечетных делителя, не считая 1 и само число(если ...
Wismut's user avatar
  • 13
0 голосов
1 ответ
216 показов

C++ программа которая выводит на экран количество простых чисел среди введённых

Пользователь вводит в с клавиатуры десять чисел больше двух, нужно что бы программа выводила количество простых чисел среди введённых Понимаю что код не правильный, но нужна максимально простая ...
Nightwalker's user avatar
0 голосов
1 ответ
54 показа

Оптимизация алгоритма "Забавная игра"

Помогите, пожалуйста, оптимизировать алгоритм по времени выполнения. Признаюсь, переписал его с питона, потому что мой выполнялся ещё дольше. Мне кажется нужно концептуально поменять решение. Вот ...
Владимир Попов's user avatar
1 голос
2 ответа
121 показ

Слишком большие числа для long long

Есть функция factorial(n), которая находит n!: long long factorial(int n) { if (n == 0) return 1; return n * factorial(n - 1); } А также функция factorization(n), которая находит ...
Thwrani's user avatar
  • 109
0 голосов
2 ответа
309 показов

Задача "Суперчисла"

Имеется задача: Суперчислом называется число, являющееся суммой двух простых чисел из диапазона [2…B]. Требуется найти все суперчисла из заданного диапазона [A…B]. (2 <= A <= B <= 40000) ...
Thwrani's user avatar
  • 109
2 голоса
2 ответа
83 показа

Почему возникает Memory Limit Exceed?

В контесте нужно решить следующую задачу: На вершине лесенки, содержащей n ступенек, сидит кузнечик, который хочет спуститься вниз, к основанию. Кузнечик умеет прыгать на следующую ступеньку, на ...
demmen's user avatar
  • 304
-1 голос
1 ответ
322 показа

Задача "Степень"

Дана задача: Для того чтобы проверить, как её ученики умеют считать, Мария Ивановна каждый год задаёт им на дом одну и ту же задачу — для заданного натурального A найти минимальное натуральное N ...
Thwrani's user avatar
  • 109
2 голоса
3 ответа
2k показов

Найти наибольший простой делитель одного целого числа БЕЗ ДЕЛЕНИЯ

Нужен простой наибольший делитель целого числа !НО по заданию нельзя использовать операции деления ( / и % ) Нужен алгоритм. не пойму от чего отталкиваться.
el Muerto de Mederti's user avatar
0 голосов
1 ответ
50 показов

Неверная работа кода при "длинных" входных данных

Всем привет. Задачка с CodeWars "Kids and candies". С условием можете ознакомиться по ссылке https://www.codewars.com/kata/56cca888a9d0f25985000036/python . Суть в том, что нужно найти НОК ...
Николай Бруцкий-Стемпковский's user avatar
0 голосов
0 ответов
312 показов

Найти обратный элемент в конечном поле

Интересует такой вопрос. У нас есть поле Галуа GF(2^8), в нем задается элемент в байтовом представлении (допустим, А = 1Е, то бишь 00011110 в двоичной системе счисления, а значит, если представлять ...
asavva's user avatar
  • 71
0 голосов
1 ответ
537 показов

Четные - нечетные (С++)

Программа получает на вход два целых положительных числа A и B, не превосходящие 2×10^9. Мне надо сделать оптимизацию, чтобы программа считывала разность четной и нечетной быстрее. Каким способом ...
reiwoo's user avatar
  • 23
-1 голос
1 ответ
175 показов

На какую максимальную степень K делится число N! через разложение на простые множители

В интернете увидел способ решения задачи, но никак не могу понять, как работает разложение на множители. Число k раскладываем на множители вида "число - степень", а после делим простые ...
Savvon's user avatar
  • 13
2 голоса
2 ответа
239 показов

Дружественные числа. Выход за временные рамки

Даны два целых положительных числа M, N. Требуется найти все «дружественные» пары чисел на отрезке [M; N]. Дружественным для числа А является такое число В, что оно равно сумме делителей А, исключая ...
Game_SHOW_LD's user avatar
2 голоса
3 ответа
191 показ

Наименьшее натуральное число, сумма делителей которого не меньше миллиона

Рассмотрим последовательность: 1, 6, 48, 360, 3120, 27720, ? Энный элемент этой последовательности равен наименьшему натуральному числу, имеющему эн-значную сумму делителей (включая 1 и само число). ...
Ян Альбертович Дененберг's user avatar
-2 голоса
2 ответа
92 показа

Как найти общие вершины двух правильных многоугольников? [закрыт]

Скажите, пожалуйста, как можно решить эту задачу. Что-то совсем не могу понять как это можно реализовать.. В окружность вписаны N-угольник и M-угольник. Известно, что многоугольники правильные и имеют ...
jassiiccaa2020's user avatar
2 голоса
4 ответа
942 показа

Посчитать количество красивых чисел

На просторах интернета нашел интересную задачу: Нужно посчитать кол-во красивых (сумма первых шести чисел равна сумме шести последних цифр) 13-значных чисел в 13-значной системе счисления, например: ...
QuickDzen's user avatar
  • 713
1 голос
1 ответ
122 показа

Подсчитать больше 8 автоморфных чисел

Задание: Автоморфными называются числа, которые содержатся в последних разрядах их квадрата, например, десятичные числа: 5^2 = 25, 25^2 = 625. Автоморфные числа существуют в системе счисления, ...
Екатерина Решетняк's user avatar
1 голос
2 ответа
682 показа

Найти сумму простых делителей числа N

При вводе любого значения ничего не выводится #include <stdio.h> #include <conio.h> int main() { int n, sum = 1; if (scanf("%lf", n) == 0) { printf("...
MicroHuman's user avatar
3 голоса
2 ответа
231 показ

Найти наименьшее екатериноекатерининское число

Натуральное число, превышающее 1, назовём екатериноекатерининским, если оно делится как на число своих делителей, так и на обоих его соседей по натуральному ряду. [то есть, если число это N, а число ...
Ян Альбертович Дененберг's user avatar
0 голосов
2 ответа
4k показов

Поиск дружественных пар чисел с помощью циклов

Составьте программу для решения задачи. Два натуральных числа называются дружественными, если каждое из них равно сумме всех делителей другого (само другое число в качестве делителя не рассматривается)...
Daniil Vlasov's user avatar
1 голос
3 ответа
419 показов

НОД чисел Фибоначчи

Помогите, пожалуйста, понять в чём ошибка. Как известно, последовательность Фибоначчи определяется следующим образом: F(0) = 0, F(1) = 1, F(n) = F(n-1)+F(n-2) (для всех n > 1). По заданным n и m ...
nikita sokolov's user avatar
0 голосов
3 ответа
773 показа

Представление натурального числа в виде суммы квадратов натуральных чисел, слишком «‎медленный» код

# Представление натурального числа # в виде суммы квадратов # натуральных чисел. k=int(input()) for i in range(1, k+1): if k==i**2: print(i) for i in range(1, k+1): for j in range(i,...
Ян Альбертович Дененберг's user avatar
3 голоса
4 ответа
536 показов

Считаем пары если заданы НОД и НОК

Код не проходит по времени. Задано два натуральных числа A и B. Найти кол-во таких пар чисел (P, Q), для которых A является НОД(P, Q), а B - НОК(P, Q). Входные данные : В единственном ряде два ...
nikita sokolov's user avatar
1 голос
2 ответа
1k показов

Задача на магический квадрат с умножением 3x3 [закрыт]

Из собеседования на джуниора, нужно было быстро решить. Я не решил, гугл не помог. Гуглится якобы решенный квадрат, но при проверке произведения там разные. Возьмем числа от трех до одиннадцати и ...
John Nix's user avatar
1 голос
1 ответ
111 показов

Не понимаю в чем ошибка, требуется вывести ответ по модулю

Программа должна найти сумму всех сочетаний, где k от 1 до l. Я использовал все через модуль. И формулу на картинке ниже. Example_1: Input: 3 1 3 Output: 7 Example_2: Input: 3 4 3 Output: 0 ...
SionM's user avatar
  • 13
3 голоса
1 ответ
1k показов

Задача Обратные числа C++

Обратное число В этой задаче нужно ответить на 1≤t≤105 запросов. Каждый запрос состоит из двух целых чисел 2≤p≤109 и 0<a<p, число p является простым. На каждый запрос нужно вывести в отдельной ...
EgorWork's user avatar
  • 140
1 голос
2 ответа
2k показов

Нахождение трех четных делителя в промежутке

Найдите все натуральные числа, принадлежащие отрезку [101 000 000; 102 000 000], у которых ровно 3 различных чётных делителей (количество нечётных делителей может быть любым). В ответе перечислите ...
Alex's user avatar
  • 27
0 голосов
1 ответ
136 показов

Time limit exeeded

Задача на acmp.ru "Осколки" На Землю надвигается страшная угроза, к нам летит облако из N огромных астероидов. Известно только то, что все они одинакового размера. У учёных есть ракеты, ...
Roman's user avatar
  • 1
1 голос
1 ответ
141 показ

Делимость n! на n^2 C++

Как проверить делимость n! на n во второй степени ( n2 )?
Brin's user avatar
  • 31
0 голосов
1 ответ
90 показов

Как высчитать степень?

я прочитал теорему как разложить простой число на множители и не понял нечего, да я знаю что здесь min, max это функции которые принимают со своих параметров наибольшие или наименьшее значения: пример ...
infinity's user avatar
1 голос
1 ответ
255 показов

Оптимизация программы поиска количества нулей в конце факториала числа

import math num = int(input()) num = math.factorial(num) countZero = 0 while (num % 10 == 0): num //= 10 countZero += 1 print(countZero)
d4riy's user avatar
  • 47
2 голоса
1 ответ
1k показов

Докажите, что количество делителей квадрата натурального числа - число нечетное

Задача: Докажите, что количество делителей квадрата натурального числа - число нечетное. Сформулируйте и докажите обратное утверждение. Указание: Все делители числа n^2, кроме одного, можно разбить ...
Bohdan Pylypenko's user avatar
0 голосов
1 ответ
48 показов

Подскажите, пожалуйста, почему этот код иногда выводит 1 вместо нужного числа

Подскажите, пожалуйста, почему этот код иногда выводит 1 вместо нужного числа. Спасибо #include <stdlib.h> #include <stdio.h> int main(){ int isicc; ...
Foss's user avatar
  • 3
0 голосов
1 ответ
1k показов

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

то есть, 1 + 2 и 2 + 1 – это один и тот же способ разложения числа Пример: Введите натуральное число: 4 Количество разложений: 4
ApTuMoLLIKa's user avatar
-1 голос
2 ответа
746 показов

Сумма цифр шестнадцатеричного числа [закрыт]

Найти однозначное число которое получается вычислением суммы цифр шестнадцатеричного числа(беззнаковое) n (повторно). Пример: 40820A2 -> 4 + 0 + 8 + 2 + 0 + A + 2 = 1A; 1A -> 1 + A = B Т.е. ...
TigerTV.ru's user avatar
  • 3,185
0 голосов
2 ответа
3k показов

Задача на С++. Минимальный простой делитель

Дано целое число, не меньшее 2. Выведите его наименьший простой делитель. Вводится целое положительное число N ≤ 2·109. Выведите ответ на задачу. Вот мой код: #include <iostream> using namespace ...
ZZZXXXXXXZZZ's user avatar
2 голоса
1 ответ
249 показов

Presentation Error на 10 тесте python

Пытаюсь решить следующую задачу в яндекс контесте В этой задаче вам нужно вычислить значение функции Эйлера от некоторого биномиального коэффициента («выбрать k элементов из n»). Формат ввода В ...
Galina's user avatar
  • 21
1 голос
3 ответа
666 показов

Помогите с задачей C++. Дано натуральное число N. Определить, если это возможно, пару x,y таких натуральных чисел, что N = x^2+y^2

Задача: Дано натуральное число N. Определить, если это возможно, пару x,y таких натуральных чисел, что N = x^2+y^2. Есть главная функция, принимает N, и должна эту N прогнать через функцию coupleXY(...
ktep222's user avatar
  • 13
-4 голоса
1 ответ
53 показа

Не могу решить задачу на C++. Постоянно выводится ответ 10000, т.е не присваивается значение

#include <iostream> using namespace std; int main () { int min =100000; for (int i = 10000; i > 0; i--) { for( int n=1; n<20; n++) { if (i%n==0) { ...
dzef's user avatar
  • 11
-2 голоса
2 ответа
46 показов

Как решить уравнение? [закрыт]

a mod x = b mod kx a <= b - заданы, необходимо найти минимальное x и затем минимальное k, где x >= 2 и k > 1 a, b <= 10^10
Ivan Pechyonkin's user avatar
0 голосов
1 ответ
421 показ

Дружественные числа

Даны два целых положительных числа M, N. Требуется найти все «дружественные» пары чисел на отрезке [M; N]. Дружественным для числа А является такое число В, что оно равно сумме делителей А, исключая ...
dark's user avatar
  • 13
0 голосов
1 ответ
39 показов

Помогите найти ошибку в функции перевода

Нужно осуществить перевод из 7ой системы счисления в десятичную. Вводил число я в виде строки, после чего переводил в число. Но на моменте перевода в 10ую систему мне выдает по итогу мусор вместо 69 В ...
stpd__prg's user avatar
3 голоса
4 ответа
173 показа

Ошибка в алгоритме

Закодил алгоритм проверки числа на то, является ли оно степенным, работает хорошо, но проверка не засчитывает 1 тест. В первой строке количество чисел которые нужно проверить, от 1 до 10 включительно, ...
Zeor6's user avatar
  • 31