传送门 没看过1053的走这儿 剪枝大法好。 1.前一个质数个数必定大于后一个质数个数。 2.前一个质数的幂必定小于后一个质数的幂。 在加上一些奇奇怪怪的乱搞就可以了。 他比我讲得好
#include<cstdio> #include<cstdlib> #include<iostream> #include<cmath> #include<cstring> #include<algorithm> #define mo 10000 #define ll long long using namespace std; struct bignum{ int a[27]; bignum(){} bignum(char *s){ memset(a,0,sizeof(a)); int l=strlen(s),cur=0,i; for (i=l-1;i-3>=0;i-=4) a[cur++]=(s[i-3]-48)*1000+(s[i-2]-48)*100+(s[i-1]-48)*10+s[i]-48; for (int j=0;j<=i;j++) a[cur]=a[cur]*10+s[j]-48; } bignum(int x){ memset(a,0,sizeof(a)); a[0]=x; } inline void operator *= (int x){ for (int i=0;i<27;i++) a[i]*=x; for (int i=0;i<26;i++){ a[i+1]+=a[i]/mo; a[i]%=mo; } } inline bool operator == (bignum x){ for (int i=0;i<27;i++) if (a[i]!=x.a[i]) return 0; return 1; } inline bool operator < (bignum x){ for (int i=26;i>=0;i--) if (a[i]!=x.a[i]) return a[i]<x.a[i]; return 0; } void print(){ int cnt=26; for (;!a[cnt]&&cnt;cnt--); printf("%d",a[cnt]); for (cnt--;cnt>=0;cnt--) printf("d",a[cnt]); printf("\n"); } }n,ans,tmp; char s[105]; int pri[]={ 1, 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101,103,107,109, 113,127,131,137,139,149,151,157,163,167, 173,179,181,191,193,197,199,211,223,227, 229,233,239,241,251 }; int bin[]={ 1,2,2,3,3,4,4,5,5,5, 5,5,6,6,6,6,6,6,6,7, 7,7,7,7,7,7,7,7,7,7, 7,7,8,8,8,8,8,8,8,8, 8,8,8,8,8,8,8,8,8,8, 8,8,8,8,8 }; ll q1,m,mx; void dfs(int k,bignum now,ll cnt,ll la){ if (cnt>mx||cnt==mx&&now<ans){ ans=now; mx=cnt; } if (k!=1) la=min(la,q1/(bin[k]-1)); ll tmp=cnt; for (int i=1;i<=la;i++){ if (k==1) q1=i; tmp+=cnt; now*=pri[k]; if (n<now) break; dfs(k+1,now,tmp,i); } } int main(){ scanf("%s",s); n=bignum(s); tmp=bignum(1); if (n==tmp){ printf("1"); return 0; } for (;tmp<n||tmp==n;) tmp*=pri[++m]; dfs(1,bignum(1),1,2*bin[m]-2); ans.print(); return 0; }