BZPRO
#5472. 数列
内存限制：128 MiB
时间限制：10 Sec
提交
提交记录
讨论
题目描述
输入一个长度为n的数组{ai}(1 <= i <= n)
问有多少个长度为n的数组{xi}(1 <= i <= n)，满足1 <= xi <= ai。
并且相邻两项的最大公约数小于等于k。
换句话说，对于1<i <= n，满足gcd(xi−1,xi) <= k。
问这样的数组{xi}有多少个，答案对1000000007取模。
输入格式
第一行两个整数n,k。接下来一行n个整数，表示数组{ai}。
1 <= ai,k <= 1000000。Sigma(ai) <= 1000000。
输出格式
一行一个整数表示这样的数组的个数，对1000000007取模。
样例
样例输入
9 2
1 2 3 4 5 6 7 8 9
样例输出
168852
数据范围与提示
BZPRO