Дано точное число делителей (n) числа, как определить наименьшее число, которое имеет n делителей?

Question

Описание проблемы: Ссылка: https://www.urionlinejudge.com.br/judge/en/problems/view/2869 Описание: 1 - делитель 6. Помимо 1, он имеет еще 3 делителя 6: 2, 3 и 6. Всего 6 имеет 4 делителя,и это наименьшее число, которое имеет 4 делителя. Говоря о делителе, учитывая число n, какое наименьшее число имеет n делителей?

Я пробовал два кода почти одинакового шаблона, в результате чего превышено ограничение по времени. Проблема дает подсказку для решения в MOD 100000007 (Bigmod), но я не могу найти способ решить в формуле BigMod.

#include <bits/stdc++.h>

using namespace std;
int divisors(int);

int main() 
{
    int input = 0,tc;
    cin>>tc;
    while(tc--){
        cin>>input;
        cout<<divisors(input)<<endl;
    }
    return 0;
}
int divisors(int input)
{
    int base = 1;
    int divisorNum = 0;
    int num = 0;
    while(divisorNum != input)
    {
        num = 0;
        for(int i = 1;i <= base; i++)
        {
            if(base%i==0)
            {
                num++;
            }
        }
        divisorNum = num;
        base++;
    }
    base-=1;
    return base;
}

Я знаю, что эта система занимает много времени для больших чисел. Но я не знаю систему сокращения времени. Точную проблему можно увидеть по этому адресу: https://www.urionlinejudge.com.br/judge/en/problems/view/2869

Answer 1

Сначала подумайте, как вы считаете делители положительного целого числа. Возьмем 12 в качестве примера.

Вы можете просто перечислить от 1 до 12 и проверить, делит ли перечисленное число 12: 1, 2, 3, 4, 6, 12. Или вы можете сделать простую факторизацию: 12 = 2^2 * 3^1. Если делитель записан в виде 2^m * 3^n, то m имеет три возможности 0, 1, 2, а n имеет две возможности 0, 1, следовательно, есть 3 * 2 = 6 делители.

Тогда какВы создаете минимальное число, например, с 24 делителями? Сначала вы делаете простую факторизацию на 24: 24 = 3 * 2 * 2 * 2. Тогда номер, который вы ищете - 2^(3-1)*3^(2-1)*5^(2-1)*7^(2-1). Таким образом, по существу вы делаете простую факторизацию для n, чтобы получить k членов и отсортировать их в порядке убывания (a_1, a_2, ..., a_k). Число, которое вы хотите, будет p_1 ^ (a_1 - 1) * p_2 ^ (a_2 - 1) * ... * p_k ^ (a_k - 1), где p_i - это i -ное простое число (т. Е. p_1 = 2, p_2 = 3, p_3 = 5, p_4 = 7...). Хотя это не строго доказано, но это «интуитивно правильно» :) (По словам моего друга, который применял математику). Строгое доказательство того, что это потребовало бы некоторой строгой математики, которая находится за пределами моих возможностей (как на данный момент), и не совсем подходит для StackOverflow.

(Примечание x ^ y означает «x в степени y», а не x xor y.)