1375: 【中级组】优美排列

Memory Limit：128 MB Time Limit：1.000 S
Judge Style：Text Compare Creator：
Submit：19 Solved：9

Description

       设有从 1 到 N 的 N 个整数，如果从这 N 个数字中成功构造出一个数组，使得数组的第 i 位 (1 <= i <= N) 满足如下两个条件中的一个，我们就称这个数组为一个优美的排列。       条件: (1)第 i 位的数字能被 i 整除                (2) i 能被第 i 位上的数字整除        现在给定一个整数 N，请问可以构造多少个优美的排列？ 样例:
输入: 2
输出: 2 解释: 第 1 个优美的排列是 [1, 2]:            第 1 个位置（i=1）上的数字是1，1能被 i（i=1）整除            第 2 个位置（i=2）上的数字是2，2能被 i（i=2）整除           第 2 个优美的排列是 [2,1]:            第 1 个位置（i=1）上的数字是2，2能被 i（i=1）整除           第 2 个位置（i=2）上的数字是1， i（i=2）能被1 整除  

Input

        输入一个数字 n 。

Output

       输出一个数字表示 1至n的n个整数总共可以构造多少个优美的排列。

Sample Input Copy 

3

Sample Output Copy 

3

HINT

提示:
  • 1 <= n <= 16