Вопросы с меткой [теория-чисел]
Теория чисел (в узком смысле) занимается свойствами целых чисел: делимостью (простые числа, НОД/НОК, сравнения по модулю), решением уравнений в целых числах (диофантовы уравнения, пифагоровы тройки). К ней же относятся цепные дроби, числа Фибоначчи (и многие другие числа с именами), большая и малая теоремы Ферма и многое, многое другое.
67
вопросов
7
голосов
3
ответа
263
показа
Программа для поиска приветливых чисел
Назовём натуральное число приветливым, если для любого натурального n⩾2
энная цифра этого числа равна остатку этого числа при делении на n
. Например, число 2123 является приветливым, так как даёт ...
0
голосов
1
ответ
76
показов
Алгоритм нахождения всех делителей большого числа
Мне попалась задача, суть такова: сложить делители числа n и сравнить сумму с самим n. Но вопрос не про это - вопрос в том, чтобы найти эти делители для огромных чисел, например, для 23_459_879_034.
...
0
голосов
1
ответ
347
показов
Алгоритм перебора чисел
Назовём нетривиальным делителем натурального числа его делитель, не равный единице и самому числу. Например, у числа 6 есть два нетривиальных делителя: 2 и 3. Найдите все натуральные числа, ...
0
голосов
3
ответа
708
показов
Найдите пять наименьших значений k, при которых N(k) имеет нечётное количество различных чётных делителей
Пусть N(k) = 1 850 000 000 + k, где k – натуральное число. Найдите пять наименьших значений k, при которых N(k) имеет нечётное количество различных чётных делителей. В ответе запишите найденные ...
1
голос
1
ответ
100
показов
возможно ли из a получить b
всем привет, есть два числа, нужно проверить возможно ли получить из числа a другое число b, умножая его на число которое делится на a и посчитать кол-во шагов за которое это можно сделать, например:
...
0
голосов
1
ответ
83
показа
Задача на gcd, не понятна логика условия
В начале игры у вас есть массив a длины n. За один ход можно выбрать два соседних элемента и заменить один из них на наибольший общий делитель этих двух чисел. То есть из двух соседних чисел x и y ...
-2
голоса
2
ответа
128
показов
Задача на автоморфные числа. Язык Си
Автоморфными называются числа, которые содержатся в последних разрядах их квадрата, например, десятичные числа: 52 = 25, 252 = 625. Автоморфные числа существуют в системе счисления, основание n ...
0
голосов
2
ответа
111
показов
Алгоритм сам завершается(хотя должен продолжаться)
Условие: Алгоритм принадлежит числовому отрезку [A;B] (1<A<B<1000000)
выводит числа,имеющие среди делителей ровно три различных натуральных нечетных делителя,
не считая 1 и само число(если ...
0
голосов
1
ответ
216
показов
C++ программа которая выводит на экран количество простых чисел среди введённых
Пользователь вводит в с клавиатуры десять чисел больше двух, нужно что бы программа выводила количество простых чисел среди введённых
Понимаю что код не правильный, но нужна максимально простая ...
0
голосов
1
ответ
54
показа
Оптимизация алгоритма "Забавная игра"
Помогите, пожалуйста, оптимизировать алгоритм по времени выполнения. Признаюсь, переписал его с питона, потому что мой выполнялся ещё дольше. Мне кажется нужно концептуально поменять решение.
Вот ...
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), которая находит ...
0
голосов
2
ответа
309
показов
Задача "Суперчисла"
Имеется задача:
Суперчислом называется число, являющееся суммой двух простых чисел из диапазона [2…B]. Требуется найти все суперчисла из заданного диапазона [A…B]. (2 <= A <= B <= 40000)
...
2
голоса
2
ответа
83
показа
Почему возникает Memory Limit Exceed?
В контесте нужно решить следующую задачу:
На вершине лесенки, содержащей n ступенек, сидит кузнечик, который хочет спуститься вниз, к основанию. Кузнечик умеет прыгать на следующую ступеньку, на ...
-1
голос
1
ответ
322
показа
Задача "Степень"
Дана задача:
Для того чтобы проверить, как её ученики умеют считать, Мария Ивановна каждый год задаёт им на дом одну и ту же задачу — для заданного натурального A найти минимальное натуральное N ...
2
голоса
3
ответа
2k
показов
Найти наибольший простой делитель одного целого числа БЕЗ ДЕЛЕНИЯ
Нужен простой наибольший делитель целого числа
!НО по заданию нельзя использовать операции деления ( / и % )
Нужен алгоритм. не пойму от чего отталкиваться.
0
голосов
1
ответ
50
показов
Неверная работа кода при "длинных" входных данных
Всем привет. Задачка с CodeWars "Kids and candies". С условием можете ознакомиться по ссылке https://www.codewars.com/kata/56cca888a9d0f25985000036/python . Суть в том, что нужно найти НОК ...
0
голосов
0
ответов
312
показов
Найти обратный элемент в конечном поле
Интересует такой вопрос. У нас есть поле Галуа GF(2^8), в нем задается элемент в байтовом представлении (допустим, А = 1Е, то бишь 00011110 в двоичной системе счисления, а значит, если представлять ...
0
голосов
1
ответ
537
показов
Четные - нечетные (С++)
Программа получает на вход два целых положительных числа A и B, не превосходящие 2×10^9.
Мне надо сделать оптимизацию, чтобы программа считывала разность четной и нечетной быстрее. Каким способом ...
-1
голос
1
ответ
175
показов
На какую максимальную степень K делится число N! через разложение на простые множители
В интернете увидел способ решения задачи, но никак не могу понять, как работает разложение на множители. Число k раскладываем на множители вида "число - степень", а после делим простые ...
2
голоса
2
ответа
239
показов
Дружественные числа. Выход за временные рамки
Даны два целых положительных числа M, N. Требуется найти все «дружественные»
пары чисел на отрезке [M; N]. Дружественным для числа А является такое число В, что
оно равно сумме делителей А, исключая ...
2
голоса
3
ответа
191
показ
Наименьшее натуральное число, сумма делителей которого не меньше миллиона
Рассмотрим последовательность: 1, 6, 48, 360, 3120, 27720, ?
Энный элемент этой последовательности равен наименьшему натуральному числу, имеющему эн-значную сумму делителей (включая 1 и само число). ...
-2
голоса
2
ответа
92
показа
Как найти общие вершины двух правильных многоугольников? [закрыт]
Скажите, пожалуйста, как можно решить эту задачу. Что-то совсем не могу понять как это можно реализовать..
В окружность вписаны N-угольник и M-угольник. Известно, что многоугольники правильные и имеют ...
2
голоса
4
ответа
942
показа
Посчитать количество красивых чисел
На просторах интернета нашел интересную задачу:
Нужно посчитать кол-во красивых (сумма первых шести чисел равна сумме шести последних цифр) 13-значных чисел в 13-значной системе счисления, например:
...
1
голос
1
ответ
122
показа
Подсчитать больше 8 автоморфных чисел
Задание: Автоморфными называются числа, которые содержатся в последних разрядах их квадрата, например, десятичные числа: 5^2 = 25, 25^2 = 625. Автоморфные числа существуют в системе счисления, ...
1
голос
2
ответа
682
показа
Найти сумму простых делителей числа N
При вводе любого значения ничего не выводится
#include <stdio.h>
#include <conio.h>
int main()
{
int n, sum = 1;
if (scanf("%lf", n) == 0)
{
printf("...
3
голоса
2
ответа
231
показ
Найти наименьшее екатериноекатерининское число
Натуральное число, превышающее 1, назовём екатериноекатерининским, если оно делится как на число своих делителей, так и на обоих его соседей по натуральному ряду. [то есть, если число это N, а число ...
0
голосов
2
ответа
4k
показов
Поиск дружественных пар чисел с помощью циклов
Составьте программу для решения задачи. Два натуральных числа называются дружественными, если каждое из них равно сумме всех
делителей другого (само другое число в качестве делителя не
рассматривается)...
1
голос
3
ответа
419
показов
НОД чисел Фибоначчи
Помогите, пожалуйста, понять в чём ошибка.
Как известно, последовательность Фибоначчи определяется следующим образом:
F(0) = 0, F(1) = 1, F(n) = F(n-1)+F(n-2) (для всех n > 1).
По заданным n и m ...
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,...
3
голоса
4
ответа
536
показов
Считаем пары если заданы НОД и НОК
Код не проходит по времени.
Задано два натуральных числа A и B. Найти кол-во таких пар чисел (P, Q), для которых A является НОД(P, Q), а B - НОК(P, Q).
Входные данные :
В единственном ряде два ...
1
голос
2
ответа
1k
показов
Задача на магический квадрат с умножением 3x3 [закрыт]
Из собеседования на джуниора, нужно было быстро решить. Я не решил, гугл не помог. Гуглится якобы решенный квадрат, но при проверке произведения там разные.
Возьмем числа от трех до одиннадцати и ...
1
голос
1
ответ
111
показов
Не понимаю в чем ошибка, требуется вывести ответ по модулю
Программа должна найти сумму всех сочетаний, где k от 1 до l. Я использовал все через модуль. И формулу на картинке ниже.
Example_1:
Input: 3 1 3
Output: 7
Example_2:
Input: 3 4 3
Output: 0
...
3
голоса
1
ответ
1k
показов
Задача Обратные числа C++
Обратное число
В этой задаче нужно ответить на 1≤t≤105
запросов. Каждый запрос состоит из двух целых чисел 2≤p≤109 и 0<a<p, число p является простым. На каждый запрос нужно вывести в отдельной ...
1
голос
2
ответа
2k
показов
Нахождение трех четных делителя в промежутке
Найдите все натуральные числа, принадлежащие отрезку [101 000 000; 102 000 000], у которых ровно 3 различных чётных делителей (количество нечётных делителей может быть любым). В ответе перечислите ...
0
голосов
1
ответ
136
показов
Time limit exeeded
Задача на acmp.ru "Осколки"
На Землю надвигается страшная угроза, к нам летит облако из N огромных
астероидов. Известно только то, что все они одинакового размера. У
учёных есть ракеты, ...
1
голос
1
ответ
141
показ
Делимость n! на n^2 C++
Как проверить делимость n! на n во второй степени ( n2 )?
0
голосов
1
ответ
90
показов
Как высчитать степень?
я прочитал теорему как разложить простой число на множители и не понял нечего,
да я знаю что здесь min, max это функции которые принимают со своих параметров наибольшие или наименьшее значения: пример ...
1
голос
1
ответ
255
показов
Оптимизация программы поиска количества нулей в конце факториала числа
import math
num = int(input())
num = math.factorial(num)
countZero = 0
while (num % 10 == 0):
num //= 10
countZero += 1
print(countZero)
2
голоса
1
ответ
1k
показов
Докажите, что количество делителей квадрата натурального числа - число нечетное
Задача:
Докажите, что количество делителей квадрата натурального числа - число
нечетное. Сформулируйте и докажите обратное утверждение.
Указание:
Все делители числа n^2, кроме одного, можно разбить ...
0
голосов
1
ответ
48
показов
Подскажите, пожалуйста, почему этот код иногда выводит 1 вместо нужного числа
Подскажите, пожалуйста, почему этот код иногда выводит 1 вместо нужного числа. Спасибо
#include <stdlib.h>
#include <stdio.h>
int main(){
int isicc;
...
0
голосов
1
ответ
1k
показов
Требуется получить и вывести на экран количество всех возможных различных способов представления этого числа в виде суммы натуральных чисел
то есть, 1 + 2 и 2 + 1 – это один и тот же способ разложения числа
Пример:
Введите натуральное число:
4
Количество разложений: 4
-1
голос
2
ответа
746
показов
Сумма цифр шестнадцатеричного числа [закрыт]
Найти однозначное число которое получается вычислением суммы цифр шестнадцатеричного числа(беззнаковое) n (повторно).
Пример:
40820A2 -> 4 + 0 + 8 + 2 + 0 + A + 2 = 1A;
1A -> 1 + A = B
Т.е. ...
0
голосов
2
ответа
3k
показов
Задача на С++. Минимальный простой делитель
Дано целое число, не меньшее 2. Выведите его наименьший простой делитель. Вводится целое положительное число N ≤ 2·109. Выведите ответ на задачу.
Вот мой код:
#include <iostream>
using namespace ...
2
голоса
1
ответ
249
показов
Presentation Error на 10 тесте python
Пытаюсь решить следующую задачу в яндекс контесте
В этой задаче вам нужно вычислить значение функции Эйлера от некоторого биномиального коэффициента («выбрать k элементов из n»).
Формат ввода
В ...
1
голос
3
ответа
666
показов
Помогите с задачей C++. Дано натуральное число N. Определить, если это возможно, пару x,y таких натуральных чисел, что N = x^2+y^2
Задача:
Дано натуральное число N. Определить, если это возможно, пару x,y таких натуральных чисел, что N = x^2+y^2.
Есть главная функция, принимает N, и должна эту N прогнать через функцию coupleXY(...
-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)
{
...
-2
голоса
2
ответа
46
показов
Как решить уравнение? [закрыт]
a mod x = b mod kx
a <= b - заданы, необходимо найти минимальное x и затем минимальное k, где x >= 2 и k > 1
a, b <= 10^10
0
голосов
1
ответ
421
показ
Дружественные числа
Даны два целых положительных числа M, N. Требуется найти все «дружественные»
пары чисел на отрезке [M; N]. Дружественным для числа А является такое число В, что
оно равно сумме делителей А, исключая ...
0
голосов
1
ответ
39
показов
Помогите найти ошибку в функции перевода
Нужно осуществить перевод из 7ой системы счисления в десятичную.
Вводил число я в виде строки, после чего переводил в число.
Но на моменте перевода в 10ую систему мне выдает по итогу мусор вместо 69
В ...
3
голоса
4
ответа
173
показа
Ошибка в алгоритме
Закодил алгоритм проверки числа на то, является ли оно степенным, работает хорошо, но проверка не засчитывает 1 тест. В первой строке количество чисел которые нужно проверить, от 1 до 10 включительно, ...