Skip to content

Instantly share code, notes, and snippets.

@asdfgh0308
Created October 16, 2012 12:57
Show Gist options
  • Save asdfgh0308/3899106 to your computer and use it in GitHub Desktop.
Save asdfgh0308/3899106 to your computer and use it in GitHub Desktop.
zoj3662长春H
#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;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment