題目描述
從文件中讀入一個正整數n(10≤n≤31000)。要求將n寫成若干個正整數之和,并且使這些正整數的乘積最大。 例如,n=13,則當n表示為4+3+3+3(或2+2+3+3+3)時,乘積=108為最大。
輸入
只有一個正整數: n (10≤n≤31000)
輸出
第1行輸出一個整數,為最大乘積的位數。 第2行輸出最大乘積的前100位,如果不足100位,則按實際位數輸出最大乘積。 (提示:在給定的范圍內,最大乘積的位數不超過5000位)。
樣例輸入
13
樣例輸出
3
108
題解
高精度
首先根據某小學奧數理論,如果n%3==0,則全拆成3;如果n%3==1,則拆出來一個4,其余全拆成3;如果n%3==2,則拆出來一個2,其余全拆成3.
然后高精度乘低精度就好了。
由于有位數限制,所以比較懶沒有壓位,可能會慢點。
#include <cstdio>
#include <cstring>
struct data
{int len , num[5010];data(){len = 0 , memset(num , 0 , sizeof(num));}data operator=(const int a){len = 1 , num[0] = a;return *this;}data operator*(const int a)const{data t;int i;for(i = 0 ; i < len ; i ++ ) t.num[i] += num[i] * a , t.num[i + 1] += t.num[i] / 10 , t.num[i] %= 10;t.len = len + (bool)t.num[len];return t;}void output(){printf("%d\n" , len);int i;for(i = len - 1 ; i >= 0 && i >= len - 100 ; i -- ) printf("%d" , num[i]);printf("\n");}
}ans;
int main()
{int n , i;scanf("%d" , &n);ans = (n + 1) % 3 + 2;for(i = 1 ; i <= (n - 2) / 3 ; i ++ ) ans = ans * 3;ans.output();return 0;
}