← 返回题目列表

Codeforces · 818/E

E. 再次卡牌游戏

中文机器翻译题面 查看原题

Vova 再次尝试玩一些电脑纸牌游戏。

这个游戏中的套牌创建规则很简单。给 Vova 一副现有的 n 张牌和一个幻数 k。牌组中的牌的顺序是固定的。每张卡片上都写有一个数字;数字ai写在这副牌中的第i张卡上。

在收到这副牌和魔法数字后,Vova从牌堆顶部移除x(可能x = 0)张牌,从牌堆底部移除y(可能y = 0)张牌,剩下的牌组就是他的新牌组(移除牌后Vova必须在牌堆中至少留下一张牌)。因此,Vova 的新牌组实际上包含原始牌组中的牌 x + 1、x + 2、... n - y - 1、n - y。

Vova 的新牌组被认为是有效的,当且仅当其新牌组中的牌上写的所有数字的乘积能被 k 整除。因此,Vova 收到了一副牌(可能不是有效牌)和一个数字 k,现在他想知道,有多少种方法可以选择 x 和 y,以便从顶部移走 x 张牌和从底部移走 y 张牌后,他得到的牌堆是有效的?

输入

第一行包含两个整数 n 和 k (1 ≤ n ≤ 100 000, 1 ≤ k ≤ 109)。

第二行包含 n 个整数 a1, a2, ..., an (1 ≤ ai ≤ 109) — 写在卡片上的数字。

输出

打印选择 x 和 y 的方法数,以便生成的牌组有效。

示例

输入 #1

3 4
6 2 8

输出 #1

4

输入 #2

3 6
9 1 14

输出 #2

1

注意

在第一个示例中,x 和 y 的可能值为:

1. x = 0, y = 0;
2. x = 1, y = 0;
3. x = 2, y = 0;
4. x = 0, y = 1。