FINDNUM - Tìm số

Tác giả: skyvn97

Ngôn ngữ: C++

#include<stdio.h>
#include<vector>
using namespace std;
typedef unsigned long long ull;
const ull INF=1e19+1;
ull pr[]={0,2,3,5,7,11,13,17,19,23,29,31};
vector<ull> p[15];
int n,i,j,k;
ull f[15][1111];
int main(void)
{
    for (i=1;i<=11;i=i+1)
        {
         p[i].push_back(1);
         p[i].push_back(pr[i]);
         while (p[i][p[i].size()-1]>p[i][p[i].size()-2])
               {
                k=p[i].size()-1;
                p[i].push_back(p[i][k]*pr[i]);               
               }
        } 
    scanf("%d",&n);
    for (i=1;i<=n;i=i+1)
        {
         if (i-1>=p[1].size()-1) f[1][i]=INF;
         else f[1][i]=p[1][i-1];
        }
    for (i=2;i<=11;i=i+1)
        for (j=1;j<=n;j=j+1)
            {
             f[i][j]=INF;
             for (k=1;k<=j;k=k+1)
                 if (j%k==0)
                    if ((k-1<p[i].size()-1) && (f[i-1][j/k]<INF))
                       if ((f[i-1][j/k]*p[i][k-1])%f[i-1][j/k]==0)
                          if (f[i][j]>f[i-1][j/k]*p[i][k-1])
                             f[i][j]=f[i-1][j/k]*p[i][k-1];                       
            }
    printf("%llu",f[11][n]);
}

Download