Brief description:

…. 将 n 做整数分拆。。使得分拆出的数的 lcm 最大。。

Analysis:

dp[i][j] 表示前 i 个素数。。和为 j 的 lcm 的最大值。。
。。取对数后背包。。

int mod;

const int PMAX = 3009;
VI P; bitset<PMAX> isP;
void sieve(){
    FOR(i, 2, PMAX){
        if (!isP[i]) P.PB(i);
        for (int j=0;j<SZ(P)&&i*P[j]<PMAX;++j){
            isP[i*P[j]]=1; if (!(i%P[j])) break;
        }
    }
}
const int M = 3009;
DB dp[M]; int dp_m[M];
int m;

int main(){

#ifndef ONLINE_JUDGE
    //freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
#endif

    sieve();

    while (~scanf("%d%d", &m, &mod)){
        fill(dp, dp+m+1, 0), fill(dp_m, dp_m+m+1, 1);
        REP(i, SZ(P)){
            if (P[i] > m) break;
            DB p = log(P[i]); DWN_1(j, m, P[i]){
                DB t = p; for (int T=P[i];T<=j;T*=P[i],t+=p) if (dp[j] < dp[j-T] + t){
                    dp[j] = dp[j-T] + t;
                    dp_m[j] = (dp_m[j-T]*T) % mod;
                }
            }
        }

        OT(dp_m[m]);
    }
}

http://acm.hust.edu.cn/vjudge/problem/viewSource.action?id=1548068

Posted by xiaodao
Category: POJ