Даны целые числа p и q. Получить все делители числа q, взаимно простые с p, т.е. не имеющие с p общих делителей.

@phenomiks · Регистрация: 16.11.2009

Author24 — интернет-сервис помощи студентам

Даны целые числа p и q. Получить все делители числа q, взаимно простые с p, т.е. не имеющие с p общих делителей.

Есть в C++ она у вас на форуме, не могли бы вы в Паскаль сделать с использованием двумерного массива: Взаимно простые делители

@LeBron23 · 27.12.2009, 17:27

Сообщение от phenomiks

Даны целые числа p и q. Получить все делители числа q, взаимно простые с p, т.е. не имеющие с p общих делителей.

Общих делителей, отличных от 1, Вы хотели сказать?
Зачем 2мерный, можно 2 одномерных, делаем факторизацию обеих чисел (получим 2 одномерных массива с простыми делителями), потом выбрасываем со второго массива все числа, которые есть в первом (если n и t - 2 из простых делителей q, то n*t будет иметь общий делитель t с числом p, если t - простой делитель числа p).
Далее битовыми масками вхождения строим все произведения. Можно или выбросить повторения потом, или с самого начала прописать степени.
Можно даже с 1 массивом, сначала розложить второе число, а потом, пока будем факторизировать первое, ничего не запоминать, а на ходу выбрасывать лишние числа с массива.
Такое решение подходит? Или обезательно 2мерный?
З.Ы. А если маленькие числа и задача не для практического применения (например, задание в школе/универе), то можно и глупое решение - перебор.

@phenomiks · 27.12.2009, 17:33 **[ТС]**

Сообщение от LeBron23

Общих делителей, отличных от 1, Вы хотели сказать?
Зачем 2мерный, можно 2 одномерных, делаем факторизацию обеих чисел (получим 2 одномерных массива с простыми делителями), потом выбрасываем со второго массива все числа, которые есть в первом (если n и t - 2 из простых делителей q, то n*t будет иметь общий делитель t с числом p, если t - простой делитель числа p).
Далее битовыми масками вхождения строим все произведения. Можно или выбросить повторения потом, или с самого начала прописать степени.
Можно даже с 1 массивом, сначала розложить второе число, а потом, пока будем факторизировать первое, ничего не запоминать, а на ходу выбрасывать лишние числа с массива.
Такое решение подходит? Или обезательно 2мерный?
З.Ы. А если маленькие числа и задача не для практического применения (например, задание в школе/универе), то можно и глупое решение - перебор.

Некоторые фразы не понял, но думаю подходит. Но можно и "по глупому", если не сложно, напиши плиз

@LeBron23 · 27.12.2009, 17:42

Сообщение от phenomiks

Некоторые фразы не понял, но думаю подходит. Но можно и "по глупому", если не сложно, напиши плиз

Что тут сказать

Подняли мне настроение.
Пока думайте дальше, когда все поймете - возьмемся за настоящее решение, а пока "глупое" ловите.

Pascal
1
2
3
4
5
6
7
8
9
10
var a,i,b,t,q:longint;
begin
readln(a,b);
for i:=1 to b do begin
if b mod i=0 then begin
t:=i;q:=a;
while (t>0)and (q>0) do if t>q then t:=t mod q else q:=q mod t;
if t+q=1 then writeln(i);
end;end;
end.

Это глупое. Хотя за секунду работает для чисел в пределах нескольких миллионов, но глупое.
Да, забыл сказать, на буквы не обращайте внимания. Назвал переменные так, как мне удобно кодить.
На входе 2 наших числа, на выходе - все ответы, по одному в строке. Если надо - можно их в массиве хранить.

Новые блоги и статьи Все статьи Все блоги /
Winforstrap или красявый дизайн своими руками на HTML+JS+Winforms anomal6 04.03.2025 Сидел тут вечером ковырял проект на MAUI, и как же глупо создаются пакеты MSIX и система обновлений пакета публикации, но не об этом. Бывает нужен современный дизайн программы а писать на MAUI,. . .	Формат данных для симуляции физики, посредством распространённых не обученных моделей. Hrethgir 04.03.2025 Что-то как-то снова потерялось, зато катангенсы закатангесились в одном сообщении. На днях писал, что планирую для работы апгрейдить (на этот раз удачно) девайс для работы (конкретно - здоровья для,. . .	Концепция variadic CoderHuligan 04.03.2025 Мне не очень нравится (а кому это нравится?) что у нас есть отдельно компилятор, отдельно линковщик, причем со своим собственным командным языком. При этом усложнении надо знать помимо языка. . .	Java Record или Kotlin Data Class: что лучше для неизменяемых данных Wired 04.03.2025 Java Record и Kotlin Data Class — два мощных инструмента для обуздания неизменяемых структур данных, каждый со своим уникальным подходом к решению этой задачи. История их появления весьма. . .	Создание производительных API с Java и gRPC Wired 04.03.2025 В мире микросервисной разработки вопрос производительности часто становится краеугольным камнем. И хотя REST API давно завоевал сердца разработчиков своей простотой и интуитивностью, при высоких. . .
Что нового в JDK 24 Wired 04.03.2025 JDK 24 — это настоящий прорыв в эволюции Java, который кардинально меняет правила игры. В этом релизе разработчики Oracle наконец-то довели до ума множество критически важных улучшений в. . .	Разработка блокчейн с использованием Java: смарт-контракты и dApp Wired 04.03.2025 Погружаясь в мир блокчейн-разработки на Java, разработчик получает доступ к внушительному арсеналу инструментов. В отличие от Solidity, который "заперт" в экосистеме Ethereum, Java предоставляет. . .	WebAssembly в Kubernetes stackOverflow 03.03.2025 В современной экосистеме облачных технологий WebAssembly (Wasm) становится все более значимым компонентом, предлагая уникальный подход к выполнению кода в распределенных системах. Эта технология. . .	GitHub Actions или Jenkins: Выбираем CI/CD платформу stackOverflow 03.03.2025 Непрерывная интеграция и развертывание (CI/ CD) изменили подход к разработке программного обеспечения, превратив его в бесшовный процесс от написания кода до развертывания в продакшн. GitHub Actions и. . .	Автоматизация тестирования Pull Request в Kubernetes: Интеграция с GitHub Actions и GKE stackOverflow 03.03.2025 Масштабные проекты с использованием Kubernetes требуют надежной системы тестирования изменений перед их внедрением в продакшн-среду. Традиционный подход с ручной проверкой Pull Request не справляется. . .

@phenomiks 1 / 1 / 0 Регистрация: 16.11.2009 Сообщений: 15
		1
	Даны целые числа p и q. Получить все делители числа q, взаимно простые с p, т.е. не имеющие с p общих делителей. 27.12.2009, 17:17. Показов 12905. Ответов 3 Метки нет (Все метки) Даны целые числа p и q. Получить все делители числа q, взаимно простые с p, т.е. не имеющие с p общих делителей. Есть в C++ она у вас на форуме, не могли бы вы в Паскаль сделать с использованием двумерного массива: Взаимно простые делители 0

@LeBron23 10 / 10 / 4 Регистрация: 18.11.2009 Сообщений: 47
	27.12.2009, 17:27	2
	Сообщение от phenomiks Даны целые числа p и q. Получить все делители числа q, взаимно простые с p, т.е. не имеющие с p общих делителей. Общих делителей, отличных от 1, Вы хотели сказать? Зачем 2мерный, можно 2 одномерных, делаем факторизацию обеих чисел (получим 2 одномерных массива с простыми делителями), потом выбрасываем со второго массива все числа, которые есть в первом (если n и t - 2 из простых делителей q, то n*t будет иметь общий делитель t с числом p, если t - простой делитель числа p). Далее битовыми масками вхождения строим все произведения. Можно или выбросить повторения потом, или с самого начала прописать степени. Можно даже с 1 массивом, сначала розложить второе число, а потом, пока будем факторизировать первое, ничего не запоминать, а на ходу выбрасывать лишние числа с массива. Такое решение подходит? Или обезательно 2мерный? З.Ы. А если маленькие числа и задача не для практического применения (например, задание в школе/универе), то можно и глупое решение - перебор. 0

@phenomiks 1 / 1 / 0 Регистрация: 16.11.2009 Сообщений: 15
	27.12.2009, 17:33 [ТС]	3
	Сообщение от LeBron23 Общих делителей, отличных от 1, Вы хотели сказать? Зачем 2мерный, можно 2 одномерных, делаем факторизацию обеих чисел (получим 2 одномерных массива с простыми делителями), потом выбрасываем со второго массива все числа, которые есть в первом (если n и t - 2 из простых делителей q, то n*t будет иметь общий делитель t с числом p, если t - простой делитель числа p). Далее битовыми масками вхождения строим все произведения. Можно или выбросить повторения потом, или с самого начала прописать степени. Можно даже с 1 массивом, сначала розложить второе число, а потом, пока будем факторизировать первое, ничего не запоминать, а на ходу выбрасывать лишние числа с массива. Такое решение подходит? Или обезательно 2мерный? З.Ы. А если маленькие числа и задача не для практического применения (например, задание в школе/универе), то можно и глупое решение - перебор. Некоторые фразы не понял, но думаю подходит. Но можно и "по глупому", если не сложно, напиши плиз 0