Всем привет! Решаю очередную задачку с сайта задач с онлайн судьей, зашел в тупик. Задание звучит следующим образом:
Цитата
Какое наименьшее число N можно представить в виде произведения N = A∙B ровно K способами? Произведения A∙B и B∙А считаются одним способом, все числа натуральные (1≤K≤50).
Ход моих мыслей был следующим:
Спойлер(Показать/Скрыть)
Любое число может быть представлено в виде произведения простых с точностью до степеней, то есть любое N = 1 * 2^a * 3^b * 5^c ..., - основная теорема арифметики.
Нам нужно начти такое число, множители которого можно разбить на 2 части K раз, да так чтобы не было двух пар a*b, b*a. Я пришел к выводу, что такое число будет вида 1 * 2^(k - 1) * 3, то есть для K = 3, результат будет равен 12 12 = 1 * 2^2 * 3 = 1 * 2 * 2 * 3, из чего мы можем получить три пары: ([1, 2*2*3], [1*2*, 2*3], [1*2*2, 3])
Исключения K = 1 и K = 2
Для K = 50, это число будет равно 1 * 2^49 * 3 = 1 * 2 * 2 * .. * 2 * 3 = 1688849860263936
Данный алгоритм проходит всего лишь 5 тестов из 13. Если кто-то видит явную ошибку в данном алгоритме, прошу привести мне пример K, для которого программа дает неверный результат, ну и указать что-же должно получиться при этом K. Если решите привести полное правильное решение или какие-либо подсказки, размещайте их пожалуйста в спойлерах. Спасибо!
код программы
Спойлер(Показать/Скрыть)
#include <math.h> #include <iostream>
using namespace std; int main() { int k; cin >> k;
long long result;
if ( k == 1 ) { result = 1; } else if ( k == 2 ) { result = 4; } else { result = 1; // pow(2, k - 1) * 3 while ( --k > 0 ) result *= 2; result *= 3; }
cout << result << endl; return 0; }
--------------------
perl -e 'print for (map{chr(hex)}("4861707079204E6577205965617221"=~/(.{2})/g)), "\n";'
прошу привести мне пример K, для которого программа дает неверный результат
Погоди.. Для k=2 по твоей формуле получаем n=6. Но, насколько я понял, ты допускаешь а=1. Тогда: 1. 1*4 2. 2*2 - и отсюда следует, что n=4. Во что я не врубился?
--------------------
я - ветер, я северный холодный ветер я час расставанья, я год возвращенья домой