题目内容

将一个整数 S 拆分,求他们最大的 lcm

解题思路

思路其实比较简单,就是一个完全背包,但是需要注意的细节很多。

第一,发现如果将 s 拆分为 a+b,且 \gcd(a,b) \not=1,则答案为 ab/\gcd(a,b)。相当于 \gcd(a,b) 这一部分就被浪费掉了,所以发现拆分出来的数选择素数或者素数的幂最佳,因为两者间必然互素。解决方案就是在进行 dp 之前先把素数筛一遍。p_i

设我们正在考虑第 i 个素数 p_iq 次方,易得状态转移方程为 f(j)=\max\lbrace f(j),f(j-p_i^q)\times p_i^q\rbrace

第二,我们最后需要的是最大的结果取模,所以如果中间过程中取模的话会出现一些玄学的问题,这个时候就需要对数出来帮忙了。

我们知道如果 ab,则 \log a+\log b<\log c+\log d。所以可以令 f(j) 存储我们取过对数的结果,ans(j) 存储真正的结果。转移方程如下:

f(j)=\max\lbrace f(j),f(j-p_i^q)+ q\log p_i \rbrace\\
ans(j)=\max\lbrace ans(j), ans(j-p_i^q)\times p_i^q \rbrace\bmod m

代码如下:

#include <cstdio>
#include <cmath>

template<class T> T max(T a,T b)
{
    return a>b?a:b;
}

int s,m,ans[3005];
double f[3005];
int prime[500];
bool is_not_prime[3005];



int main()
{
    int cnt=0;
    for(int i=2;i<=3005;i++)
    {
        if(!is_not_prime[i])
            prime[++cnt]=i;
        for(int j=1;j<=cnt && prime[j]*i<=3005;j++)
        {
            is_not_prime[prime[j]*i]=1;
            if(i%prime[j]==0)
                break;
        }
    }//欧拉筛
    while(scanf("%d %d",&s,&m)!=EOF)
    {
        for(int i=0;i<=s;i++)
            f[i]=0,ans[i]=1;
        for(int i=1;i<=cnt && prime[i]<=s;i++)
            for(int j=s;j>=prime[i];j--)
            {
                double tmp=log(prime[i]*1.0);//取log
                for(int p=prime[i],q=1;p<=j;p*=prime[i],q++)//取p的q次方
                {
                    if(f[j-p]+q*tmp>f[j])
                    {
                        f[j]=f[j-p]+q*tmp;//更新取了对数的f
                        ans[j]=(ans[j-p]*p)%m;//更新真正答案
                    }
                }
            }
        printf("%d\n",ans[s]);
    }
    return 0;
}
最后修改日期:2020年9月19日

作者

留言

撰写回覆或留言

发布留言必须填写的电子邮件地址不会公开。