IPB
ЛогинПароль:

 
 Ответить  Открыть новую тему 
> Теория чисел, разбиение на множители
сообщение
Сообщение #1


Perl. Just code it!
******

Группа: Пользователи
Сообщений: 4 100
Пол: Мужской
Реальное имя: Андрей

Репутация: -  44  +


Всем привет!
Решаю очередную задачку с сайта задач с онлайн судьей, зашел в тупик. Задание звучит следующим образом:

Цитата
Какое наименьшее число N можно представить в виде произведения N = A∙B ровно K способами? Произведения A∙B и B∙А считаются одним способом, все числа натуральные (1≤K≤50).


Ход моих мыслей был следующим:
Спойлер (Показать/Скрыть)

Данный алгоритм проходит всего лишь 5 тестов из 13.
Если кто-то видит явную ошибку в данном алгоритме, прошу привести мне пример K, для которого программа дает неверный результат, ну и указать что-же должно получиться при этом K. Если решите привести полное правильное решение или какие-либо подсказки, размещайте их пожалуйста в спойлерах.
Спасибо!


код программы
Спойлер (Показать/Скрыть)



--------------------
perl -e 'print for (map{chr(hex)}("4861707079204E6577205965617221"=~/(.{2})/g)), "\n";'
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #2


Уникум
*******

Группа: Пользователи
Сообщений: 6 823
Пол: Мужской
Реальное имя: Лопáрь (Андрей)

Репутация: -  159  +


Цитата(klem4 @ 21.03.2011 18:41) *
прошу привести мне пример K, для которого программа дает неверный результат

Погоди..
Для k=2 по твоей формуле получаем n=6. Но, насколько я понял, ты допускаешь а=1. Тогда:
1. 1*4
2. 2*2
- и отсюда следует, что n=4.
Во что я не врубился? blink.gif


--------------------
я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #3


Perl. Just code it!
******

Группа: Пользователи
Сообщений: 4 100
Пол: Мужской
Реальное имя: Андрей

Репутация: -  44  +


Я же указал, что
Цитата
Исключения K = 1 и K = 2

rolleyes.gif


--------------------
perl -e 'print for (map{chr(hex)}("4861707079204E6577205965617221"=~/(.{2})/g)), "\n";'
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #4


Гость






Цитата
прошу привести мне пример K, для которого программа дает неверный результат
Да без проблем... (Показать/Скрыть)
 К началу страницы 
+ Ответить 
сообщение
Сообщение #5


Perl. Just code it!
******

Группа: Пользователи
Сообщений: 4 100
Пол: Мужской
Реальное имя: Андрей

Репутация: -  44  +


Круто, спасибо)


--------------------
perl -e 'print for (map{chr(hex)}("4861707079204E6577205965617221"=~/(.{2})/g)), "\n";'
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #6


Perl. Just code it!
******

Группа: Пользователи
Сообщений: 4 100
Пол: Мужской
Реальное имя: Андрей

Репутация: -  44  +


Устала меня эта задача smile.gif Сдал с небольшими читами, для самых сложных чисел, именно формулу вывести мне не удалось sad.gif
ограничение по времени 1с, по памяти 64мб.

Спойлер (Показать/Скрыть)


Сообщение отредактировано: klem4 -


--------------------
perl -e 'print for (map{chr(hex)}("4861707079204E6577205965617221"=~/(.{2})/g)), "\n";'
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 

 Ответить  Открыть новую тему 
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0

 




- Текстовая версия 24.05.2018 7:00
Хостинг предоставлен компанией "Веб Сервис Центр" при поддержке компании "ДокЛаб"