• [D] Friends

  • 时间限制: 2000 ms　内存限制: 196605 K
  • 问题描述

  • There are N people stand in a line. The ith person has a number Pi. If the Pi and Pj have a common prime factor X when

    [p(i + 1) … p(j - 1)] can not be divisible by X, we will call the ith person and the jth person is a couple of friends.

    Two numbers l and r can divide the line into 3 parts, [1 … l], [l + 1 … r - 1] and [r … N]. We call [1 … l] and [r … N] block A,

    [l + 1 … r - 1] block B, and we define F(l , r) as the number of the couples in A minus the number of the couples in B.

    Now, I have a favorite number C, can you figure out how many groups of l and r satisfies F(l , r)=C?

  • 输入
  • The first line contains two space-separated integers N (1≤N≤5000) and C — the number of people and the favorite number.
    The second line contains n space - separated integers P1, P2, ..., Pn (1 ≤ Pi ≤ 10^7), Pi is the ith person's number.
  • 输出
  • Print a single integer — the answer to the problem.
  • 样例输入
  • 10 2
1 2 3 4 5 5 4 3 2 1
9 2
1 3 6 7 15 4 12 1 14
  • 样例输出
  • 4
4
  • 提示
  • In the second sample. In total, 7 pairs friends among the 9 persens, (2,3), (3,5), (3,6), (4,9), (5,7), (6,7), (7,9).
when (l=1 and r=5) or (l=3 and r=7) or (l=5 and r=8) or (l=5 and r=9) is satisfies F(l, r)=2. 
So, the answer of the sample is 4.
  • 来源
  • 岁月静好@DLMU
  • 操作

显示春菜