Spirala OJI X 2003

/// Aceasta sursa obtine 100p pe kilonova, cu 67ms timp executie.
/// Constrangerile de pe infoarena sunt mai stricte asadar acolo obtine doar 80p (deci exista inca o optimizare).
#include <fstream>
#include <algorithm>
#include <iomanip>
using namespace std;
typedef long long ll;
ifstream cin("spirala.in");
ofstream cout("spirala.out");
ll v[51][51], desfasurat[51*51], ciclu[51][51], frecv[1200], factori[200];
ll n , k, found, nrdesf, nr_factori;
ll sol = 1e18;
void desfasoara()
{
    int p = 0;
    for(int it = 1;it<=n/2;it++)
    {
        /// De la stanga la dreapta
        for(int i = it;i <= n - it + 1;i++)
            desfasurat[++p] = v[it][i];
        /// De sus in jos
        for(int i = it + 1; i <= n - it + 1; i++)
            desfasurat[++p] = v[i][n-it+1];
        /// De la dreapta la stanga
        for(int i = n - it; i >= it; i--)
            desfasurat[++p] = v[n-it+1][i];
        /// De jos in sus
        for(int i = n - it; i > it; i--)
            desfasurat[++p] = v[i][it];
    }
    if(n % 2 == 1) desfasurat[++p] = v[n/2+1][n/2+1];
}

void amesteca()
{
    for(int i = 1;i<=n;i++)
        for(int j = 1;j<=n;j++)
        {
            if(i % 2 == 1)
                v[i][j] = desfasurat[(i-1)*n + j];
            else v[i][j] = desfasurat[i * n - j + 1];
        }
}
void identice()
{
    for(int i = 1;i<=n;i++)
        for(int j = 1;j<=n;j++)
            if(ciclu[i][j] == 0)
            {
                if(i % 2 == 1 && v[i][j] == (i-1)*n + j)
                    ciclu[i][j] = nrdesf, found++;
                else if(i % 2 == 0 && v[i][j] == i * n - j + 1)
                    ciclu[i][j] = nrdesf, found++;
            }
}
void afisare(int mat[51][51], const int& nr = 0)
{
    if(nr!=0)
        cout << "MATRICEA #" << nr << ": \n";
    for(int i = 1;i<=n;i++, cout << '\n')
        for(int j = 1;j<=n;j++)
            cout << setw(3) << mat[i][j] << ' ';
}
void find_cycles()
{
    while(found != n*n)
    {
        nrdesf++;
        desfasoara();
        amesteca();
        identice();
        //afisare(v,nrdesf);
    }
}

void backtracking(const int& index, const ll& current_lcm)
{
    if(current_lcm > 2e9)
        return;
    if(index == nr_factori+1) /// au fost toti factorii procesati.
    {
        int sum = 0;
        for(int i = 1;i<=nr_factori;i++)
            if(current_lcm % factori[i] == 0)
                sum += frecv[factori[i]];
        if(sum == k)
            sol = min(sol, current_lcm);
        return;
    }
    backtracking(index+1, current_lcm);
    ll new_lcm = current_lcm * factori[index] / __gcd(current_lcm,factori[index]);
    backtracking(index+1,new_lcm);
    return;
}
int main()
{
    cin >> n >> k;
    for(int i = 1;i<=n;i++)
        for(int j = 1;j<=n;j++)
        {
            if(i % 2 == 1)
                v[i][j] = (i-1)*n + j;
            else v[i][j] = i * n - j + 1;
        }
    // afisare(v);
    find_cycles();
    /*cout << "CICLURI" << '\n';
    //afisare(ciclu); */

    for(int i = 1;i<=n;i++)
        for(int j = 1;j<=n;j++)
            frecv[ciclu[i][j]]++;

    /*for(int i = 1;i<=nrdesf; i++)
        if(frecv[i]!=0)
            cout << i << " : " << frecv[i] << '\n';*/

    /// Solutia va fi cmmmc dintre o submultime de numere
    /// {p_1, p_2 ,... p_n} , 1 <= p_i <= nrdesf
    /// pentru care frecv[p_1] + frecv[p_2] + ... frecv[p_n] = k

    /// Stim ca cmmmc este numarul obtinut din
    /// exponentii cei mai mari pentru fiecare numar prim din
    /// descompunerile in factori primi ale numerelor alese.

    /// Asadar solutia problemei se va putea scrie sub forma
    /// sol = d_1 ^ p_1 * d_2 ^ p_2 * ... * d_n ^ p_n.

    /// Deoarece solutia se garanteaza a fi <= 2e9 inseamna ca
    /// cmmmc{p_1,p_2,..,p_n} <= 2e9 .

    /// Observam ca nu putem avea foarte multi factori primi distincti
    /// In solutie deoarece creste foarte rapid numarul rezultat.
    /// 2 * 3 * 5 * 7 * 11 * 13 * 17 * 19 * 23 * 29 > 2e9
    /// Cu alte cuvinte putem avea maxim 9 factori primi distincti.

    /// Cu cat avem mai multi factori cu atat puterile factorilor vor
    /// fi mai mici astfel incat sa se respecte sol <= 2e9 si astfel,
    /// Un algoritm de backtracking optimizat va putea explora intreg
    /// search-space-ul fara a depasi limita de timp.

    /// Un algoritm simplu de backtracking ne arata ca numarul de solutii <= 2e9 este
    /// cel mult 164k si ca numarul de apelari al functiei este in jur de 1.4 mil.

    for(int i = 1;i<=nrdesf;i++)
        if(frecv[i]!=0)
            factori[++nr_factori] = i;
    backtracking(1,1);
    cout << sol << '\n';
    return 0;
}