Count UVA - 1645

发布时间 2023-04-11 14:01:27作者: towboat

 

  f[n] = sum{ f[i] } ( (n-1)%i==0) 

 f[1]=1

#include <iostream>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std ; 
 const int N =1e3+2,mod=1e9+7;
int f[N];
 int sov(int n){
 	if(n==1) return 1;
 	if(~f[n]) return f[n];
 	
 	int s=0;
 	for(int i=1;i<n;i++){
 		if((n-1)%i==0) s+=sov((n-1)/i),s%=mod;
 	}
 	return f[n]=s;
 }
 signed main(){
 	int n;memset(f,-1,sizeof f);
 	int cas=0;
 	while(cin>>n){
 		printf("Case %d: %d\n",++cas,sov(n)) ;
 	}
 }