hdu 3092 Least common multiple

时间:2021-08-26 06:45:00

思路:

容易知道,分解成素数的lcm肯定是最大的,因为假设分解成2个合数,设定x为他们的 最大公约数,

那么他们的最小公倍数就要减少x倍了
然后如果是素数之间的最小公倍数,那么就只是他们的乘积,同样的n分解,没有 除的肯定比有除的大,

因此可以得到结论 所以可以先晒一次素数,然后用这些素数填满那个n
这里填满也很容易想到是背包问题了,因为同一个素数可以用几次,所以就是一个 典型的多重背包了,

就是dp[j] = lcm(dp[j - k] , dp[k]);
然后还有一个问题,就是对于所有素数取lcm,会导致结果很大,超int的 而且虽然有取mod,

那么转移方程变为dp[j] = dp[j - k] * w * prime[i]; 都是乘法运算,那么我们就可以利用取对数,

把乘法运算转成加法来判断了就行了 然后另开一个数组,用来取mod的,最后结果就是dp[n]了

代码如下:

 #include<cstdio>
#include<vector>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#define M 10005
using namespace std;
double dp[M];
int p[M];
int prime[M],cnt,n;
bool f[M];
void init()
{
cnt=;
for(int i=;i<M;i++){
if(!f[i]) prime[cnt++]=i;
for(int j=;j<cnt&&i*prime[j]<M;j++){
f[i*prime[j]]=;
if(i%prime[j]==) break;
}
}
}
void solve(int m)
{
memset(dp,,sizeof(dp));
for(int i=;i<=n;i++) p[i]=;
for(int i=;i<cnt&&prime[i]<=n;i++){
double t=log(prime[i]);
for(int j=n;j>=prime[i];j--){
for(int k=prime[i],num=;k<=j;k*=prime[i],num++)
if(dp[j-k]+t*num>dp[j]){
dp[j]=dp[j-k]+t*num;
p[j]=p[j-k]*k%m;
}
}
}
}
int main()
{
int m;
init();
while(scanf("%d%d",&n,&m)!=EOF){
solve(m);
printf("%d\n",p[n]);
}
return ;
}