5.greatest
题目描述
已知若干个正整数的和为S,求这若干个正整数的最小公倍数的最大值。
输入
第一行一个整数T,表示测试数据的组数。
接下来T行,每行包括一个正整数S,表示若干个正整数的和为S。
输出
输出T行,每行包括一个整数,表示和为S的若干个正整数的最小公倍数的最大值。
样例输入
2
4
7
样例输出
4
12
数据范围限制
样例中第一组数据S=4,它能分解成S=1+1+1+1,S=1+1+2,S=1+3,S=2+2,S=4,很明显S=4时最小公倍数为4,是所有情况中最小公倍数最大的;第二组数据S=7,它能分解成S=3+4,3和4的最小公倍数是12,也是所有情况中最小公倍数最大的。
提示
40%的数据:S≤100;
80%的数据:S≤330,结果不会超过long long类型;
100%的数据:2≤S≤500,T≤10,结果不会超过25位整数。
正解
首先要证明选的数只能是质数的任意次幂。
证明非常简单,因为最小的质数是二,而对于任意的两个质数x1、x2,他们的幂次为y1、y2,都有
x1y1+x2y2<x1y1乘x2y2
也就是说,选任意的合数都不如选它的分解质因数合算。
比如选24,不如选2,2,2,3合算。
然后得到了这个证明,我们就可以继续往下做。
DP:设f[i]表示i最多可以组成多大的数,我们可以得到以下转移方程:
7 (f[7-22]=f[3])乘22=12
f[i]=max{f[i-jk]*(jk)}(j∈素数,j^k<=i)
于是,我们可以先预处理出500以内的素数,在进行以上DP,最后处理询问。
注意:
由于DP的无后效性,循环i时要倒序。
小技巧
这里,我们要用高精度,但我们可以用个东西
__int128
这个东西最大是128位数的整型,可以乘,可以加……
但是有一些注意事项
1.不能用cin和scanf输入,要手写输入函数
2.不能用cout和printf输出,要手写输出函数(就像下面一样)
void sc(__int128 x)//输出代码
{
o=0;
while(x!=0)
{
c[++o]=x%10;
x=x/10;
}
for(int i=o;i>=1;i--)
cout<<c[i];
cout<<endl;
}
3.Dev—C++上面运行会错误,但在评测网站上就OK(网站例洛谷、gmoj等等)
AC代码
#include<iostream>
#include<cstdio>
using namespace std;
long long t,s,o,tot,a[1005],b[1005],c[1005];
__int128 f[1005];
void sc(__int128 x)//输出函数
{
o=0;
while(x!=0)
{
c[++o]=x%10;
x=x/10;
}
for(int i=o;i>=1;i--)
cout<<c[i];
cout<<endl;
}
int main()
{
freopen("greatest.in","r",stdin);
freopen("greatest.out","w",stdout);
for(int i=2;i<=500;i++)//筛选法
if(a[i]==0)
{
b[++tot]=i;
for(int j=i+i;j<=500;j+=i)
a[j]=1;
}
for(int i=0;i<=500;i++)f[i]=1; //初值
for(int i=tot;i>=1;i--)//质数
for(int j=500;j>=b[i];j--)
for(int k=b[i];k<=j;k*=b[i])//质数的幂
if(k<=j)f[j]=max(f[j],f[j-k]*k);
cin>>t;
for(int i=1;i<=t;i++)
{
cin>>s;
sc(f[s]);//直接用输出函数输出
}
return 0;
}
下面附本次比赛的其它题目
2020.03.04模拟赛12(第一题)
2020.03.04模拟赛12(第二题)
2020.03.04模拟赛12(第三题)
2020.03.04模拟赛12(第四题)
2020.03.04模拟赛12(第五题)
2020.03.04模拟赛12(总结)