hdu 3092 Least common multiple（完全背包+数论） Least common multiple

86 阅读 0 评论 57 点赞

我是靠谱客的博主过时羽毛，最近开发中收集的这篇文章主要介绍hdu 3092 Least common multiple（完全背包+数论） Least common multiple，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

Least common multiple

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 437 Accepted Submission(s): 162

Problem Description

Partychen like to do mathematical problems. One day, when he was doing on a least common multiple(LCM) problem, he suddenly thought of a very interesting question: if given a number of S, and we divided S into some numbers , then what is the largest LCM of these numbers? partychen thought this problems for a long time but with no result, so he turned to you for help!
Since the answer can very big,you should give the answer modulo M.

Input

There are many groups of test case.On each test case only two integers S( 0 < S <= 3000) and M( 2<=M<=10000) as mentioned above.

Output

Output the largest LCM modulo M of given S.

Sample Input


6 23

Sample Output


6
Hint: you can divied 6 as 1+2+3 and the LCM(1,2,3)=6 is the largest so we output 6%23=6.

题意：给你第一个数n，问你把n分解成另外几个数字，求这几个数字最大的LCM（最小公倍数），结果对m取模

思路：首先我们可以明确的是n分成的这几个数字必然是互质的，为什么？假设有两个数字a和b不互质，那么两者的gcd必然不为1，求LCM是必然会少乘以一个两者的gcd，最后的解也就肯定不是最优解了。而对于多个互质的数，最小公倍数是他们的乘积，所以我们可以先筛选出1~3000的素数，然后从这些素数里面取或者多个组成n，最后求n填满时最大的LCM

发现什么了吗？是不是很像完全背包？没错，这里就是用的完全背包。

只不过跟一般的完全背包不同的是一般的背包取k件相同物品（体积和价值为p），体积和价值都是p*k，而这里因为p是n的约数，两个p意味着一个合数p*p

所以这里需要对n~小于等于n的某个素数做一次比较，当体积价值为p,p^1,p^3...p^k时最大的ans[i]

注意这道题运算过程中会溢出，而又不能随时取模，随时取模会导致比较最大值时出错。所以我们可以令设一个数组，将乘法转换为加法。同时维护两个数组即可

代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
#define N 3500
#define LL long long
double dp[N];
LL ans[N];
LL prime[N],notprime[N];
LL gcd(LL a,LL b)
{
return b?gcd(b,a%b):a;
}
void init()
{
prime[0]=0;
for(int i=2;i<=3000;i++)
{
if(!notprime[i])
{
prime[++prime[0]]=i;
for(LL j=(LL)i*i;j<=3000;j+=i)
notprime[j]=1;
}
}
}
int main()
{
int n,m;
init();
while(scanf("%d %d",&n,&m)!=EOF)
{
for(int i=0;i<=n;i++)
{
dp[i]=0;
ans[i]=1;
}
for(LL i=1;i<=prime[0]&&prime[i]<=n;i++)
{
double tmp=log(prime[i]*1.0);
for(LL j=n;j>=prime[i];j--)
{
for(LL k=prime[i],q=1;k<=j;k*=prime[i],q++)
{
if(dp[j-k]+q*tmp>dp[j])
{
dp[j]=dp[j-k]+q*tmp;
ans[j]=ans[j-k]*k%m;
}
}
}
}
printf("%lldn",ans[n]);
}
return 0;
}