这个问题之前看过。。。尽量拆成3。。
然后。。。高精度没有压位居然过了。。
1 #include<bits/stdc++.h> 2 #define lowbit(a) ((a)&(-(a))) 3 #define clr(a,x) memset(a,x,sizeof(a)) 4 #define rep(i,l,r) for(int i=l;i<(r);i++) 5 typedef long long ll; 6 using namespace std; 7 int read() 8 { 9 char c=getchar(); 10 int ans=0,f=1; 11 while(!isdigit(c)){ 12 if(c=='-') f=-1; 13 c=getchar(); 14 } 15 while(isdigit(c)){ 16 ans=ans*10+c-'0'; 17 c=getchar(); 18 } 19 return ans*f; 20 } 21 int n,cnt,re,a[5009]; 22 int main() 23 { 24 n=read(); 25 cnt=n/3;re=n%3; 26 if(re==1||!re){ 27 re+=3; 28 cnt--; 29 } 30 a[0]=1; 31 rep(i,0,cnt){ 32 rep(i,0,5009) a[i]*=3; 33 rep(i,0,5008) if(a[i]>9){ 34 a[i+1]+=a[i]/10; 35 a[i]%=10; 36 } 37 } 38 rep(i,0,5009) a[i]*=re; 39 rep(i,0,5008) if(a[i]>9){ 40 a[i+1]+=a[i]/10; 41 a[i]%=10; 42 } 43 int l; 44 for(int i=5008;~i;i--){ 45 if(a[i]){ 46 l=i; 47 break; 48 } 49 } 50 printf("%d ",l+1); 51 for(int i=l;~i&&l-i<100;i--) putchar('0'+a[i]); 52 puts(""); 53 return 0; 54 }
1263: [SCOI2006]整数划分
Time Limit: 1 Sec Memory Limit: 162 MBSubmit: 908 Solved: 453
[Submit][Status][Discuss]
Description
从文件中读入一个正整数n（10≤n≤31000）。要求将n写成若干个正整数之和，并且使这些正整数的乘积最大。 例如，n=13，则当n表示为4+3+3+3（或2+2+3+3+3）时，乘积=108为最大。
Input
只有一个正整数： n （10≤n≤31000）
Output
第1行输出一个整数，为最大乘积的位数。 第2行输出最大乘积的前100位，如果不足100位，则按实际位数输出最大乘积。 （提示：在给定的范围内，最大乘积的位数不超过5000位）。
Sample Input
13
Sample Output
3
108
108