FINDNUM - Tìm số

Tác giả: flashmt

Ngôn ngữ: C++

#include<iostream>
using namespace std;
int n,a[100],b[100],m,p[1000],np,aa[100],bb[100];
long long re;

void att(int m)
{
     int i,j,k,q;
     long long s=1;
     q=0;
     for (i=1;i<=m;i++)
     {
         aa[i]=a[i]; bb[i]=b[i];
     }
     for (i=1;i<m;i++)
      for (j=i+1;j<=m;j++)
       if (aa[i]>aa[j])
       {
          k=aa[i]; aa[i]=aa[j]; aa[j]=k;
          k=bb[i]; bb[i]=bb[j]; bb[j]=k;
       }
     for (i=m;i>=1;i--)
      if (s<re)
      for (j=1;j<=bb[i];j++)
      {
          q++;
          for (k=1;k<aa[i];k++) 
          {   
              s*=p[q];
              if (s>=re) break;
          }
          if (s>=re) break;
      }
     if (s<re) re=s;       
     for (i=1;i<=m;i++)
      for (j=i;j<=m;j++)
       if (b[i]>0 && b[j]>0)
       {
          if (i==j && b[i]==1) continue;
          b[i]--; b[j]--;
          q=0;
          for (k=1;k<=m;k++)
            if (a[k]==a[i]*a[j])
            {
               q=k; break;
            }
          if (q) 
          {
              b[q]++; att(m);
          }
          else
          {
              a[m+1]=a[i]*a[j]; b[m+1]=1;
              att(m+1);
          }
          if (q) b[q]--;
          else b[m+1]--;
          b[i]++; b[j]++;
       }
}

int main()
{
    int i,j;
    cin >> n;
    m=0; np=0;
    for (i=2;i<=n;i++)
    {
        if (n%i==0)
        {
          m++; a[m]=i;
          while (n%i==0)
          {
             n/=i; b[m]++;
          }
        }
    }
    for (i=2;i<=1000;i++)
    {
        bool kt=true;
        for (int j=2;j*j<=i;j++)
           if (i%j==0)
           {
              kt=false; break;
           }
        if (kt)
        {
          np++; p[np]=i;
        }
    }
    re=1000000000; re*=re; 
    att(m);
    cout << re << endl;
    return 0;
}

Download