Se consideră un număr natural N care este par.

Cerința

Să se determine cel mai mic număr natural impar M care are același număr de divizori ca și N.

Date de intrare

Programul citește de la tastatură numărul N.

Date de ieșire

Programul va afișa pe ecran cel mai mic număr natural impar M care are același număr de divizori ca și N.

Restricții și precizări

• 1 ≤ N ≤ 1 000 000 000 și este par
• Se garantează că M va fi mai mic decât 2 000 000 000

Exemplu

Intrare

360

Ieșire

3465

Explicație

360 are 24 de divizori. Cel mai mic număr impar care are tot 24 de divizori este 3465.

#include <bits/stdc++.h>

using namespace std;
#define Inf 2000000000

int nrd[101], n;
long long minim = Inf;
int prime[] = {2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97};

long long calcnr (int ind)
{
    int aux;
    long long nr = 1;
    for (int i = ind, l = 1; i >= 1; i --, l ++)
    {
        aux = nrd[i];
        while (aux > 1)
        {
            nr *= prime[l];
            aux --;
            if (nr > Inf)return Inf;
        }
    }
    return nr;
}
void back(int x, int ind)
{
    if (x == 1)
    {
        minim = min(minim, calcnr(ind));
        return;
    }
    nrd[ind + 1] = x;
    back(1, ind + 1);
    for(int i = 0; prime[i] * prime[i] <= x && prime[i] <= x/prime[i]; i ++)
        if (x % prime[i] == 0)
        {
            nrd[ind + 1] = prime[i];
            back(x / prime[i], ind + 1);
        }
}
int main()
{
    cin >> n;
    int div = 2, nrdiv = 1, x;
    while(n > 1)
    {
        if(n % div == 0)
        {
            x = 0;
            while(n % div == 0) x++ , n /= div;
            nrdiv *= (x + 1);
        }
        div ++;
    }
    back(nrdiv, 0);
    cout << minim;
    return 0;
}