首页 > 代码库 > Hdu 2189

Hdu 2189

2024-08-03 02:59:50   220人阅读

Problem地址：http://acm.hdu.edu.cn/showproblem.php?pid=2189

 

题意不难，就是将一个数拆分成若干个素数的和（数字可以有重复），问能几种拆分的方法。

第一眼看到一不小心就认为是Dfs，结果自然是超时。

后来仔细想了一下，题目之要求求出有几种，没有什么其他要求。而Dfs更适用与要求求出具体哪些素数相加得的题更合适。题目也说了，假设人与人之间是没区别的，因此我想到了生成函数。使用生成函数，这题看上去就简单许多了。

 

#include <iostream>#include <cmath>#include <cstring>#include <cstdio>using namespace std;const int MAXN = 150 + 5;int c1[MAXN], c2[MAXN];bool Is_prime( int n ){    int k = sqrt( n );    int i;    for( i=2;i<=k;i++ )    {        if( n%i==0 )        {            return false;        }    }    return true;}int main(){    int i,j,k;    memset( c1,0,sizeof(c1) );    for( i=0;i<MAXN;i+=2 )    {        c1[i] = 1;    }    memset( c2, 0, sizeof(c2) );    for( i=3;i<MAXN;i++ )    {        if( Is_prime(i)==false )            continue;        for( j=0;j<MAXN;j++ )        {            for( k=0;k+j<MAXN;k+=i )            {                c2[ k+j ] += c1[ j ];            }        }        for( j=0;j<MAXN;j++ )        {            c1[j] = c2[j];            c2[j] = 0;        }    }    int N;    int T;    cin >> T;    while( T-- )    {        cin >> N;        cout << c1[N] << endl;    }    return 0;}

 

Hdu 2189


联系
我们