UVA_1575

https://vjudge.net/problem/UVA-1575

枚举答案（k）、、对k质因数分解，质数的指数为cnt[i]，若n==A(tot_cnt,tot_cnt) / A(cnt[i]>1)，则该ans=k

 #include <cstring>

 #include <cstdio>

 #define LL long long

 inline void read(LL &x)

 {

     x=; register char ch=getchar();

     for(; ch>''||ch<''; ) ch=getchar();

     for(; ch>=''&&ch<=''; ch=getchar()) x=x*+ch-'';

 }

 const int N(1e6+);

 LL n,m,k,cnt[N],num,tmp;

 inline LL check(LL x)

 {

     num=tmp=; memset(cnt,,sizeof(cnt));

     for(LL i=; i<=x; ++i)

     {

         if(x%i==)

         {

             cnt[++num]++;

             for(x/=i; x%i==; )

                 x/=i,cnt[num]++;

         }

     }

     for(LL i=; i<=num; ++i) tmp+=cnt[i];

     LL tot=;

     for(LL i=; i<=tmp; ++i) tot*=i;

     for(LL i=; i<=num; ++i)

      if(cnt[i]>) for(LL j=; j<=cnt[i]; ++j) tot/=j;

     return tot;

 }

 int Presist()

 {

     freopen("C.in","r",stdin);

     freopen("C.out","w",stdout);

     read(n);

     for(k=; k<N; ++k)

         if(check(k)==n) break;

     printf("%d\n",k);

     return ;

 }

 int Aptal=Presist();

 int main(int argc,char*argv[]){;}

20分。

搜索、记录当前的方案数，合成的k，指数质数上限，要使用的质数，质数个数

从最小的质数开始枚举，可以发现，方案数与质数的指数和有关，

假设前i-1个种质数用了k个，有cnt种方案，第i种质数选a个，

那么前i种质数的方案就有cnt*c[k+a][a]

要求k最小，则小的质数指数越小越好、

 #include <cstdio>

 typedef unsigned long long LL;

 int p[]={,,,,,,,,,,,,,,,,,,,};

 LL ans,n,c[][];

 void DFS(LL k,LL cnt,int lim,int num,int tot)

 {

     if(k>ans) return ;

     if(cnt==n) { ans=k; return ; }

     if(num>=||cnt>n) return ;

     LL tmp=;

     for(int i=; i<=lim; ++i)

     {

         tmp*=p[num];

         if(k>ans/tmp) return ;

         DFS(k*tmp,cnt*c[tot+i][i],i,num+,tot+i);

     }

 }

 int Presist()

 {

     c[][]=;

     for(int i=; i<; ++i)

     {

         c[i][]=;

         for(int j=; j<=i; ++j)

             c[i][j]=c[i-][j-]+c[i-][j];

     }

     for(;~scanf("%lld",&n); )

     {

         if(n==)

         { printf("1 2\n");continue; }

         ans=(LL)<<;

         DFS(,,,,);

         printf("%lld %lld\n",n,ans);

     }

     return ;

 }

 int Aptal=Presist();

 int main(int argc,char*argv[]){;}

巴特西

UVA_1575

https://vjudge.net/problem/UVA-1575

最新文章

热门文章