hdu 4427 Math Magic dp - c++编程基础

长春现场赛的题目，dp[i][j][k]表示公倍数为i，和为j，用了k个数的方法数。

但是状态太多，注意到只有m的约数的公倍数才有可能是m，那么可以预处理出m的所以约数，然后只遍历这些状态，再稍微优化一下常数就可以过了。

#include   
#include   
#include   
#include   
#include   
using namespace std;  
const int maxn=1e3+9,N=1000,mod=1e9+7;  
int n,m,K;  
int stack[maxn],end;  
int dp[2][maxn][maxn],c[maxn][maxn];  
int mm[maxn];  
int gcd(int a,int b)  
{  
    int tmp;  
    while(a%b)  
    {  
        tmp=a%b;  
        a=b;  
        b=tmp;  
    }  
    return b;  
}  
void get()  
{  
    for(int i=1;i<=N;i++)  
    for(int j=1;j<=N;j++)  
    c[i][j]=i*j/gcd(i,j);  
}  
int main()  
{  
//    freopen("in.txt","r",stdin);  
    get();  
    while(scanf("%d%d%d",&n,&m,&K)!=EOF)  
    {  
        end=0;  
        for(int i=1;i<=m;i++)  
        if(m%i==0)  
        stack[++end]=i;  
        memset(dp,0,sizeof(dp));  
        int now=1,to=0;  
        dp[to][1][0]=1;  
        for(int k=0;k




mod)  
                dp[to][c[i][stack[p]]][j+stack[p]]-=mod;  
            }  
        }  
//        cout<