#include <bits/stdc++.h>
using namespace std;
/*从后往前递归,超时*/
int calc(int pre_num,int curlen,int k){
int sum = 0;
if(curlen == 1)
return 1;
for(auto i = 1;i < pre_num;++i){
if(pre_num % i != 0)
sum += calc(i,curlen - 1,k);
}
for(auto i = pre_num;i < k+1;++i)
sum += calc(i,curlen - 1,k);
return sum;
}
int main(){
int n,k;
while(cin >> n >> k){
cout<<calc(1,n+1,k)<<endl;
}
return 0;
}
解法二：DP
#include <bits/stdc++.h>
using namespace std;
const int mod = 1000000007;
int func(int n,int k){
/*dp[i][j]表示长度为i,以j结尾的序列数*/
vector< vector<int> > dp(n+1,vector<int>(k+1,0));
for(auto i = 1;i < k+1;++i)
dp[1][i] = 1;
for(auto i = 2;i < n+1;++i){
int sum = 0;
for(auto j = 1;j < k+1;++j){
sum = (sum + dp[i-1][j]) % mod;
}
for(auto j = 1;j < k+1;++j){
int p = 2;
int invalid = 0;
while(p * j < k+1){
invalid = (invalid + dp[i-1][p*j] % mod) % mod;
++p;
}
dp[i][j] = (sum - invalid + mod) % mod;
}
}
int ans = 0;
for(auto i = 1;i < k+1;++i)
ans = (ans + dp[n][i]) % mod;
return ans;
}
int main(){
int n,k;
while(cin >> n >> k){
cout<<func(n,k)<<endl;
}
return 0;
}
