题目：

Alien 的思想真的很诡异。 对于一个 1..N 的排列，Alien 们会把它们全部+1，变成 2..N+1 的 Alien 排列，然后考虑这个排列的优美程度。我们称 Alien 排列的第 i 个数为 Ai，一个排列的是优美的当且仅当对于 i=1..N，i 可以整除 Ai。

现在 Alien 给出一个 N，请你求一下 N 长度的优美排列个数。

Input

一行一个数 N，表示长度为 N。

Output

一行一个数 Ret，表示优美排列个数。

Samples

输入数据

5

输出数据

3

数据范围：

对于 30%数据 N≤10

对于 100%数据 N≤3000

两份代码：

#include <bits/stdc++.h>
using namespace std;
int n,daan;
bool p[3001];

void dfs(int dep)
{
	if(dep>n)
	{
		daan++; 
		return ;
	}
	for(int i=max(dep,2);i<=n+1;i+=dep)
	{
		if(!p[i])
		{
			p[i]=1;
			dfs(dep+1);
			p[i]=0;
		}
	}
}
int main()
{
	cin>>n;
	dfs(1);
	cout<<daan;
	return 0;
}
//从小到大搜索TLE了

#include <bits/stdc++.h>
using namespace std;
int n,daan;
bool p[3001];

void dfs(int dep)
{
	if(dep==0)
	{
		daan++; 
		return ;
	}
	for(int i=max(2,dep);i<=n+1;i+=dep)
	{
		if(!p[i])
		{
			p[i]=1;
			dfs(dep-1);
			p[i]=0;
		}
	}
}
int main()
{
	cin>>n;
	dfs(n);
	cout<<daan;
	return 0;
}
//从大到小搜索为什么就能过？？

没有用 latex,见谅