Закон Ома

@andrey_sax · Регистрация: 13.02.2018

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

Задача: Найти количество способов (как параллельно, так и последовательно) соединить два резистора(R1, R2) с целым положительным сопротивлением так, чтобы сопротивление схемы равнялось целому числу R.

Ограничение по времени: 1 секунда

Входные данные: число $https://www.cyberforum.ru/cgi-bin/latex.cgi?1 \leq R \leq 10^9$

Выходные данные: Искомое число способов.

Например: для 6 - ответ: 8. Пояснение: последовательно можно соединить резисторы с сопротивл. 1 и 5, 2 и 4, 3 и 3; параллельно: 7 и 42, 8 и 24, 9 и 18, 10 и 15, 12 и 12. Всего 8.

Очевидно, что кол-во способов последовательного соед. это R/2. Осталось эффективно посчитать кол-во для параллельного соединения, у меня есть алгоритм работающий за $https://www.cyberforum.ru/cgi-bin/latex.cgi?O(R)$ , но в 1 секунду не укладываюсь. Помогите найти эффективное решение.

@Ромаха · 13.02.2018, 21:23

Спорим, что человек, прочитавший тему и не знающий закон ома, забьет и не пойдет гуглить (а если потратит 30 секунд на поиск ничего путного не найдет (и снова забьет))
Так что уважайте чужое время - коли осознаете как получается 7 и 42 и прочие - объясните логику. Сразу (мне) она не ясна. А разбираться в тонкостях богомерзкой (для меня) физики - ой как не хоцца

@andrey_sax · 13.02.2018, 21:39 **[ТС]**

Знаю. Глупо поступил. "Закон ома" это название олимпиадной задачи и отношения к самой сути задания вообще не имеет (вопрос к составителю задачи). Но лучше найти название для темы я не придумал(

Последовательное соединение : R = R1 + R2
Параллельное соединение: 1/R = 1/R1 + 1/R2

Теперь, надеюсь ,все ясно.

@Shamil1 · 14.02.2018, 01:34

Количество параллельных соединений зависит только от количества простых множителей и их степеней. Но общую формулу с ходу вывести не удалось. Поэтому предлагаю два варианта.

1.
Выписываем все простые сомножители.
Например, для 18 = 2, 3, 3
Из них всеми возможными способами выбираем две группы.
Для 18: 2,3,3 и -; 2,3 и 3; 3,3 и 2; 2,3 и -; 3,3 и -; 2 и -; 3 и -; - и -; Всего 8 уникальных вариантов. Это и есть ответ.
(Можно уникальность проверять делением произведения большей группы на меньшую, считая пустую группу за 1. Результат деления равен R₁/R₂)

2.
Выписываем все простые сомножители. Откладываем в сторону те, которые встречаются 1 раз. Остальные заменяем на самые маленькие простые числа (чтобы их произведение было как можно меньше). Перемножаем и вычисляем ответ для получившегося числа (проверяя все варианты от R+1 до 2R). Это a₀. a_i+1 = 3a_i - 1. Вычисляем a_n, где n - это количество отложенных множителей. Это и есть ответ.
(То есть, для получения a₀ считаем степени всех множителей, сортируем по убыванию, возводим 2 в первую, 3 во вторую, 5 в третью и так далее)
Например, для 99 = 3*3*11: считаем для числа 4, получаем 3. 3*3-1 = 8.
Для числа 248430 = 7*7*13*13*2*3*5: считаем для числа 2*2*3*3, получаем 13. 13*3-1=38. 38*3-1=113. 113*3-1=338.

з.ы. Расчёты не проверял. Мог где-нибудь ошибиться.

@Ромаха · 14.02.2018, 06:15

Тогда и от меня вариант

C++
1
2
3
4
5
6
7
8
9
10
11
ll f;
    cin >> f;
 
    ll p = f+1, k = 0;
    double q = f*p*1.0/(p-f);
    while(p <= q) {
        if (f*p%(p-f) == 0 && f*p/(p-f) >= p) k++;
        p++;
        q = f*p*1.0/(p-f);
    }
    cout << k << endl;

Добавлено через 55 минут
Ах да, еще есть замечательный сайтик. Если просчитать первые члены и вбить в поиск - то будет вам счастье тыц

@Shamil1 · 14.02.2018, 11:02

Сообщение от Ромаха

х да, еще есть замечательный сайтик. Если просчитать первые члены и вбить в поиск - то будет вам счастье тыц

По ссылке есть формула:
If n = (p1^a1)(p2^a2)...(pt^at), a(n) = ((2*a1 + 1)(2*a2 + 1) ... (2*at + 1) + 1)/2.

Новые блоги и статьи Все статьи Все блоги /
Уведомление о неверно выбранном значении справочника Maks 06.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "НарядПутевка", разработанного в конфигурации КА2. Задача: уведомлять пользователя, если в документе выбран неверный склад. . .	Установка Qt Creator для C и C++: ставим среду, CMake и MinGW без фреймворка Qt 8Observer8 05.04.2026 Среду разработки Qt Creator можно установить без фреймворка Qt. Есть отдельный репозиторий для этой среды: https:/ / github. com/ qt-creator/ qt-creator, где можно скачать установщик, на вкладке Releases:. . .	AkelPad-скрипты, структуры, и немного лирики.. testuser2 05.04.2026 Такая программа, как AkelPad существует уже давно, и также давно существуют скрипты под нее. Тем не менее, прога живет, периодически что-то не спеша дополняется, улучшается. Что меня в первую очередь. . .	Отображение реквизитов в документе по условию и контроль их заполнения Maks 04.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "ПланированиеСпецтехники", разработанного в конфигурации КА2. Данный документ берёт данные из другого нетипового документа. . .
Фото всей Земли с борта корабля Orion миссии Artemis II kumehtar 04.04.2026 Это первое подобное фото сделанное человеком за 50 лет. Снимок называют новым вариантом легендарной фотографии «The Blue Marble» 1972 года, сделанной с борта корабля «Аполлон-17». Новое фото. . .	Вывод диалогового окна перед закрытием, если документ не проведён Maks 04.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "СписаниеМатериалов", разработанного в конфигурации КА2. Задача: реализовать программный контроль на предмет проведения документа. . .	Программный контроль заполнения реквизитов табличной части документа Maks 02.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "СписаниеМатериалов", разработанного в конфигурации КА2. Задача: 1. Реализовать контроль заполнения реквизита. . .	wmic не является внутренней или внешней командой Maks 02.04.2026 Решение: DISM / Online / Add-Capability / CapabilityName:WMIC~~~~ Отсюда: https:/ / winitpro. ru/ index. php/ 2025/ 02/ 14/ komanda-wmic-ne-naydena/

@andrey_sax 0 / 0 / 0 Регистрация: 13.02.2018 Сообщений: 2

	Закон Ома 13.02.2018, 18:47. Показов 1592. Ответов 5 Метки нет (Все метки) Задача: Найти количество способов (как параллельно, так и последовательно) соединить два резистора(R1, R2) с целым положительным сопротивлением так, чтобы сопротивление схемы равнялось целому числу R. Ограничение по времени: 1 секунда Входные данные: число $https://www.cyberforum.ru/cgi-bin/latex.cgi?1 \leq R \leq 10^9$ Выходные данные: Искомое число способов. Например: для 6 - ответ: 8. Пояснение: последовательно можно соединить резисторы с сопротивл. 1 и 5, 2 и 4, 3 и 3; параллельно: 7 и 42, 8 и 24, 9 и 18, 10 и 15, 12 и 12. Всего 8. Очевидно, что кол-во способов последовательного соед. это R/2. Осталось эффективно посчитать кол-во для параллельного соединения, у меня есть алгоритм работающий за $https://www.cyberforum.ru/cgi-bin/latex.cgi?O(R)$ , но в 1 секунду не укладываюсь. Помогите найти эффективное решение. 0

@Ромаха 354 / 135 / 28 Регистрация: 16.12.2012 Сообщений: 607 Записей в блоге: 1
	13.02.2018, 21:23
	Спорим, что человек, прочитавший тему и не знающий закон ома, забьет и не пойдет гуглить (а если потратит 30 секунд на поиск ничего путного не найдет (и снова забьет)) Так что уважайте чужое время - коли осознаете как получается 7 и 42 и прочие - объясните логику. Сразу (мне) она не ясна. А разбираться в тонкостях богомерзкой (для меня) физики - ой как не хоцца 0

@andrey_sax 0 / 0 / 0 Регистрация: 13.02.2018 Сообщений: 2
	13.02.2018, 21:39 [ТС]
	Знаю. Глупо поступил. "Закон ома" это название олимпиадной задачи и отношения к самой сути задания вообще не имеет (вопрос к составителю задачи). Но лучше найти название для темы я не придумал( Последовательное соединение : R = R1 + R2 Параллельное соединение: 1/R = 1/R1 + 1/R2 Теперь, надеюсь ,все ясно. 0

@Shamil1 Модератор 3136 / 2283 / 469 Регистрация: 26.03.2015 Сообщений: 8,886
	14.02.2018, 01:34
	Количество параллельных соединений зависит только от количества простых множителей и их степеней. Но общую формулу с ходу вывести не удалось. Поэтому предлагаю два варианта. 1. Выписываем все простые сомножители. Например, для 18 = 2, 3, 3 Из них всеми возможными способами выбираем две группы. Для 18: 2,3,3 и -; 2,3 и 3; 3,3 и 2; 2,3 и -; 3,3 и -; 2 и -; 3 и -; - и -; Всего 8 уникальных вариантов. Это и есть ответ. (Можно уникальность проверять делением произведения большей группы на меньшую, считая пустую группу за 1. Результат деления равен R₁/R₂) 2. Выписываем все простые сомножители. Откладываем в сторону те, которые встречаются 1 раз. Остальные заменяем на самые маленькие простые числа (чтобы их произведение было как можно меньше). Перемножаем и вычисляем ответ для получившегося числа (проверяя все варианты от R+1 до 2R). Это a₀. a_i+1 = 3a_i - 1. Вычисляем a_n, где n - это количество отложенных множителей. Это и есть ответ. (То есть, для получения a₀ считаем степени всех множителей, сортируем по убыванию, возводим 2 в первую, 3 во вторую, 5 в третью и так далее) Например, для 99 = 3311: считаем для числа 4, получаем 3. 33-1 = 8. Для числа 248430 = 771313235: считаем для числа 2233, получаем 13. 133-1=38. 383-1=113. 113*3-1=338. з.ы. Расчёты не проверял. Мог где-нибудь ошибиться. 0