zoj3662长春H

gistfile1.cpp

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;

int n,m,k,totpri,totfac,f[2][40][1010];
int pas,now,i,j,r,l,tp,newsta;

int svpri[10],mulpri[10],fac[100],svsta[100];

const int mod=1000000007;

void getpri(int m){
     int i;
     for(i=2;i<=m;i++)if (m%i==0){
        if (i>m) break;
        svpri[++totpri]=i;
        mulpri[totpri]=1;
        while(m%i==0){
           mulpri[totpri]*=i;
           m/=i;
        }
        //printf("  %d %d %d\n",totpri,svpri[totpri],mulpri[totpri]);
     }
}   

void getfac(int m){
     int i,j,k;
     for(i=1;i<=m;i++)if (m%i==0){
        fac[++totfac]=i;
        k=0;
        for(j=1;j<=totpri;j++){
           if (i%mulpri[j]==0) k=k|(1<<(j-1));
        }
        svsta[totfac]=k;
        //printf("%d %d\n",fac[totfac],k);
     }
}


int main(){
    while(scanf("%d%d%d",&n,&m,&k)!=EOF){
        totpri=0;
        getpri(m);//素因数
        tp=(1<<totpri)-1;
        totfac=0;
        getfac(m);//约数
        
        memset(f[1],0,sizeof(f[1]));
        
        pas=1;
        f[1][0][n]=1;
        for(i=1;i<=k;i++){
            now=1-pas;
            memset(f[now],0,sizeof(f[now]));
            for(j=0;j<=tp;j++){
               for(r=1;r<=totfac;r++){
                   newsta=j|svsta[r];
                   
                   for(l=n;l>=1;l--){
                      if (fac[r]>l) break;
                      if (f[pas][j][l]) 
                      f[now][newsta][l-fac[r]]=((long long)f[now][newsta][l-fac[r]]+f[pas][j][l])%mod;
                   }
               }
            }
            pas=now;
        }
        printf("%d\n",f[now][tp][0]);
    }
    return 0;
}