题目 https://cn.vjudge.net/problem/HYSBZ-1263
题意
给你一个n 让你拆成若干数 使他们乘积最大
思路
如果能整除3 拆3最大 否则拆1个或2个2 在拆3
算乘积可以用大数模拟 学FFT学啥了 直接用了FFT
#include <bits/stdc++.h>using namespace std;
typedef long long ll;
const double PI = acos(-1.0);
struct Complex
{double x,y;Complex(double _x = 0.0,double _y = 0.0){x = _x;y = _y;}Complex operator - (const Complex &b) const{return Complex(x - b.x, y - b.y);}Complex operator + (const Complex &b) const{return Complex(x + b.x, y + b.y);}Complex operator * (const Complex &b) const{return Complex(x * b.x - y * b.y, x*b.y + y*b.x);}
};
void change(Complex y[], int len)
{int i,j,k;for(i=1,j=len/2; i < len-1; i++){if(i < j){swap(y[i],y[j]);}k = len/2;while(j >= k){j -= k;k /= 2;}if(j < k){j += k;}}return ;
}void fft(Complex y[],int len,int on)
{change(y,len);for(int h = 2; h<=len; h<<=1){Complex wn(cos(-on*2*PI/h),sin(-on*2*PI/h));for(int j = 0; j<len; j+=h){Complex w(1,0);for(int k = j; k<j+h/2; k++){Complex u = y[k];Complex t = w*y[k+h/2];y[k] = u+t;y[k+h/2] = u-t;w = w*wn;}}}if(on == -1){for(int i = 0; i < len; i++){y[i].x /= len;}}
}
const int maxn = 1<<14;
Complex x[5*maxn],y[5*maxn];
int a[5*maxn];
ll sum[5*maxn];
ll siz[5*maxn];
int main()
{int t,n,m;scanf("%d",&n);int poo = 1;while(n % 3 != 0&&n > 0){poo*=2;n -= 2;}m = n / 3;int len = 1 << 13;x[0] = Complex(3,0);y[0] = Complex(1,0);for(int i = 1; i < len; i++)x[i] = Complex(0,0);for(int i = 1; i <= len; i++)y[i] = Complex(0,0);fft(x,len,1);fft(y,len,1);
// cout<<m<<endl;while(m){if(m % 2 == 1){for(int i = 0; i < len; i++)y[i] = x[i]*y[i];fft(y,len,-1);for(int i = 0; i < len; i++)sum[i] = (int)(y[i].x + 0.5);for(int i = 0; i < len; i++){sum[i+1] += sum[i] / 10;sum[i] %= 10;}for(int i = 0;i < len;i++)y[i] = Complex(sum[i],0);fft(y,len,1);}for(int i = 0; i < len; i++)x[i] = x[i]*x[i];fft(x,len,-1);for(int i = 0; i < len; i++)sum[i] = (int)(x[i].x + 0.5);for(int i = 0; i < len; i++){sum[i+1] += sum[i] / 10;sum[i] %= 10;}for(int i = 0;i < len;i++)x[i] = Complex(sum[i],0);fft(x,len,1);m /= 2;}fft(y,len,-1);for(int i = 0; i < len; i++)sum[i] = (int)(y[i].x + 0.5);for(int i = 0;i < len; i++)sum[i] *= poo;for(int i = 0; i < len; i++){sum[i+1] += sum[i] / 10;sum[i] %= 10;}while(len > 0&&sum[len] == 0)len--;printf("%d\n",len+1);for(int i = len,j = 0; i >= 0; i--,j++){if(j == 100) break;printf("%d",sum[i]);}return 0;
}