[ZOJ2069]Greatest Least Common Multiple

题目大意：

给定一个正整数\(n\)，将其分成若干个正整数之和，最大化这些数的LCM。保证答案小于\(10^{25}\)。

思路：

由于答案\(\le10^{25}\)，则\(n\le540\)。

可以证明一定存在一种方案使得拆分后各数互质且答案最大。

\(f[i][j]\)表示考虑前\(i\)种质数，组成的和为\(j\)的答案。转移时枚举从\(n\)中拆出这个质数的多少次方。

由于OJ上不支持__int128，所以直接最后打表即可。

打表程序：

#include<cstdio>

#include<cctype>

#include<numeric>

#include<algorithm>

inline int getint() {

	register char ch;

	while(!isdigit(ch=getchar()));

	register int x=ch^'0';

	while(isdigit(ch=getchar())) x=(((x<<2)+x)<<1)+(ch^'0');

	return x;

}

const int N=541,P=N;

typedef long long int64;

typedef __int128 int128;

int128 f[P][N];

int128 gcd(const int128 &a,const int128 &b) {

	return b?gcd(b,a%b):a;

}

inline int128 lcm(const int128 &a,const int128 &b) {

	return a/gcd(a,b)*b;

}

void print(const int128 &x) {

	if(x>9) print(x/10);

	putchar(x%10+'0');

}

bool vis[N];

int p[P];

inline void sieve() {

	for(register int i=2;i<N;i++) {

		if(!vis[i]) p[++p[0]]=i;

		for(register int j=1;j<=p[0]&&p[j]*i<N;j++) {

			vis[p[j]*i]=true;

			if(i%p[j]==0) break;

		}

	}

}

int main() {

	sieve();

	std::fill(&f[0][0],&f[0][N],1);

	for(register int i=1;i<=p[0];i++) {

		f[i][0]=f[i-1][0];

		for(register int j=1;j<N;j++) {

			f[i][j]=std::max(f[i-1][j],f[i][j-1]);

			for(register int q=p[i];q<=j;q*=p[i]) {

				f[i][j]=std::max(f[i][j],f[i-1][j-q]*q);

			}

		}

	}

	putchar('{');

	for(register int i=0;i<N;i++) {

		if(i!=0) putchar(',');

		putchar('"');print(f[p[0]][i]);putchar('"');

	}

	puts("};");

	return 0;

}