问题2073--倍数序列

2073: 倍数序列

时间限制: 1 Sec  内存限制: 128 MB
提交: 3  解决: 2
[提交] [状态] [讨论版] [命题人:]

题目描述

有一个数列a1, a2,…,an，现在要从其中取出若干个数，从小到大排序后，要求后一个数是前一个数的倍数。
假设取出了k个数(1≤k≤n)，从小到大排序后是b1, b2,… ,bk。我们要求这些数满足如下条件:对i=2,3,……,k，bi是bi-i的倍数。满足这个条件的序列b称作倍数序列。(只有1个数也算是倍数序列)
问有多少种不同的倍数序列?

输入

第一行，一个整数n(1<=n<=5000)
第二行为n个正整数a1,a2,...,an （每个正整数都<=1018）

输出

输出不同的倍数序列个数。

样例输入 Copy 

5
3 12 4 1 20

样例输出 Copy 

15

来源/分类

40动态规划杂类 
[提交] [状态]