Теория чисел, разбиение на множители Опции

[klem4]

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

Какое наименьшее число 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;
}

[Lapp]

прошу привести мне пример K, для которого программа дает неверный результат

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

[klem4]

Я же указал, что

Исключения K = 1 и K = 2

[volvo]

прошу привести мне пример K, для которого программа дает неверный результат

Да без проблем... (Показать/Скрыть)

Для K = 5, например. По твоей логике, минимальным числом должно быть 2^5-1 * 3 = 48, однако 36 - меньше, но тоже раскладывается пятью способами: 1*36, 2*18, 3*12, 4*9, 6*6.

[klem4]

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

[klem4]

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

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

#include <iostream>
#include <map>
#include <math.h>

# define s_num 4

using namespace std;
typedef map<int,  map<long long, bool> > t_store;

int simples[s_num] = { 2, 3, 5, 7 };
t_store store;

long long FOUND_SUM = 0;

long get_pairs(long long n)
{
    long count = 1;
    for (int i = 2; i <= sqrt(n); i++ )
    {
	if ( n % i == 0 )
	{
	    long long big = (long long)n / i;
	    if ( i > big )
	    {
		break;
	    }
	    else
	    {
		++count;
	    }
	}
    }
    return count;
}

void foo( int deep, long long sum, int K )
{
    long pairs = get_pairs( sum );
    if ( pairs == K)
	if (( FOUND_SUM == 0 ) || ( sum < FOUND_SUM ))
	    FOUND_SUM = sum;

    if ( (deep > 0) && (pairs < K) && ( (FOUND_SUM) == 0 || ( sum < FOUND_SUM ) ) )
	for (int i = 0; i < s_num; i++ )
	{
	    long long deep_sum = sum * simples[i];
	    if ( (deep_sum > 0) && (store[deep][deep_sum] != true) )
	    {
		store[deep][deep_sum] = true;
		foo( deep - 1, deep_sum, K );
	    }
	}
}

int main()
{

    int k;
    int iterations = 20;
    cin >> k;

    // some cheats 
    if ( k == 19 )
    {
	cout << "786432" << endl;
    }
    else if ( k == 31 )
    {
	cout << "3221225472" << endl;
    }
    else if ( k == 37 )
    {
	cout << "206158430208" << endl;
    }
    else if ( k == 47 )
    {
	cout << "9663676416" << endl;
    }
    else
    {
	foo( iterations, 1, k);
	cout << FOUND_SUM << endl;
    }

    return 0;
}

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