题解 P2563 【[AHOI2001]质数和分解】

· · 题解

感谢DengTJ童鞋指出了原题解的错误

于是我赶快把我那篇题解皮的地方改了回来。。

这个题目其实是完全背包求方案数的问题

首先呢为了让我的题解不被打回去,我先来一波分析

思路其实很明确，先把数据范围（200）以内的素数放入数组

打表和用函数判断都可以，可是个人不推荐打表，当然你愿意我也不阻拦你，打表也是能AC的；

以下是判断素数的函数

bool pan(int x)
{
    for(int i=2;i<=sqrt(x);i++)
        if(x%i==0) return 0;
    return 1;
}

很简洁有木有 好吧，大佬的比我的更好

接下来是重点，重点，重点！！！ 重要的事情说三遍

很多人不知道状态转移方程f[j]+=f[j-su[i]]的意义

可以这么理解，一个数要拆成若干素数和，等同于拆成所有该数减去一个素数差的方案数之和(转自某位大佬)

举个例子：

模拟一下7质因数分解

f[0]=1//初始化

f[1]=0//1不能被任何质数分解

f[2]=1//2能被2分解

f[3]=1//被3分解

f[4]=1//被2分解

f[5]=2//这里就是重点了，5能被5分解，也能被2，3分解

而你自己举个数，模拟一遍，自然而然就知道是怎么累加方案数的了！！！（学不懂的东西，模拟是好方法）

一定要记得初始化f[0]=1否则会WA

话不多说，上AC代码：

#include<iostream>
#include<cstring> 
#include<cmath>
using namespace std;
int su[201],f[201];
bool pan(int x)
{
    for(int i=2;i<=sqrt(x);i++)
        if(x%i==0) return 0;
    return 1;
}
int main()
{
    int n;
    while(cin>>n)
    {
        int num=0;
        for(int i=2;i<=n;i++)
            if(pan(i))
                su[++num]=i;        
        memset(f,0,sizeof(f));
        f[0]=1;
        for(int i=1;i<=num;i++)
        {
            for(int j=su[i];j<=200;j++)
                f[j]+=f[j-su[i]];
        }
        cout<<f[n]<<endl;
    }
    return 0;
}