首页 » OI » 正文

质数和分解解题报告

【题目】
见白书,没看过的蛋蛋颜会来找你的!
【分析】
DP(是个人都知道)。
类似于完全背包。(具体看代码注释)
【代码】
program zsh;
var
    b:array[0..20000] of boolean; //储存质数
    i,j,k,l,n:longint;
    f:array[0..20000] of longint; //代表表达式的数目
procedure sf(n:longint); //筛法求质数
    begin
        fillchar(b,sizeof(b),true);
        b[0]:=false;
        b[1]:=false;
        for i:=2 to n do
          if b[i] then for j:=2 to (n div i) do b[i*j]:=false;
    end;
begin
    readln(n);
    sf(n);
    f[0]:=1;
    for i:=2 to n do begin
        if b[i] then for j:=i to n do inc(f[j],f[j-i]); //此处,i为完全背包中的重量,f[i]为价值
    end;
    writeln(f[n]);
end.

发表评论