UVA_1575

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

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

 1 #include <cstring>
 2 #include <cstdio>
 3 
 4 #define LL long long
 5 inline void read(LL &x)
 6 {
 7     x=0; register char ch=getchar();
 8     for(; ch>'9'||ch<'0'; ) ch=getchar();
 9     for(; ch>='0'&&ch<='9'; ch=getchar()) x=x*10+ch-'0'; 
10 }
11 const int N(1e6+5);
12 LL n,m,k,cnt[N],num,tmp;
13 inline LL check(LL x)
14 {
15     num=tmp=0; memset(cnt,0,sizeof(cnt));
16     for(LL i=2; i<=x; ++i)
17     {
18         if(x%i==0)
19         {
20             cnt[++num]++;
21             for(x/=i; x%i==0; )
22                 x/=i,cnt[num]++;
23         }
24     }
25     for(LL i=1; i<=num; ++i) tmp+=cnt[i];
26     LL tot=1;
27     for(LL i=2; i<=tmp; ++i) tot*=i;
28     for(LL i=1; i<=num; ++i)
29      if(cnt[i]>1) for(LL j=1; j<=cnt[i]; ++j) tot/=j;
30     return tot;
31 }
32 int Presist()
33 {
34     freopen("C.in","r",stdin);
35     freopen("C.out","w",stdout);
36     read(n);
37     for(k=2; k<N; ++k)
38         if(check(k)==n) break;
39     printf("%d
",k);
40     return 0;
41 }
42 
43 int Aptal=Presist();
44 int main(int argc,char*argv[]){;}

20分。

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

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

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

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

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

 1 #include <cstdio>
 2 
 3 typedef unsigned long long LL;
 4 int p[20]={2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71};
 5 LL ans,n,c[70][70];
 6 
 7 void DFS(LL k,LL cnt,int lim,int num,int tot)
 8 {
 9     if(k>ans) return ;
10     if(cnt==n) { ans=k; return ; }
11     if(num>=20||cnt>n) return ;
12     LL tmp=1;
13     for(int i=1; i<=lim; ++i)
14     {
15         tmp*=p[num];
16         if(k>ans/tmp) return ;
17         DFS(k*tmp,cnt*c[tot+i][i],i,num+1,tot+i);
18     }
19 }
20 
21 int Presist()
22 {
23     c[0][0]=1;
24     for(int i=1; i<70; ++i)
25     {
26         c[i][0]=1;
27         for(int j=1; j<=i; ++j)
28             c[i][j]=c[i-1][j-1]+c[i-1][j];
29     }
30     for(;~scanf("%lld",&n); )
31     {
32         if(n==1)
33         { printf("1 2
");continue; }
34         ans=(LL)1<<63;
35         DFS(1,1,63,0,0);
36         printf("%lld %lld
",n,ans);
37     }
38     return 0;
39 }
40 
41 int Aptal=Presist();
42 int main(int argc,char*argv[]){;}

——每当你想要放弃的时候，就想想是为了什么才一路坚持到现在。