ID: 1595

传统题

1000ms

256MiB

难度: 7

上传者:

标签>

组合数学

数论

欧几里得算法

容斥原理

题目描述

给一个正整数数列a长度为n,求所有正整数数对（x，y）的个数，其中任意一个数对（x，y）(其中0<x<y<k)都满足:

\exist i \in \lparen0，n\rbrack，m_i|x+y

其中"|"为整除

输入格式

共三行

第一行，两个正整数n,k

第二行，n个正整数，其中第i个整数表示 $a_i$

输出格式

一个整数，表示满足条件的数对(x,y)的个数，答案对2 $^3$ $^2$ 取模

样例组

输入 #1

2 6

3 7

输出 #1

8

输入 #2

5 1000

2 3 4 5 6

输出 #2

366165

输入 #3

6 1000000000000000

2 3 5 8 13 21

输出 #3

145781088

提示说明

对于所有数据

$1 \le n \le 22$

$2 \le a_i \le10^{16}$

$k\le10^{16}$

测试点编号	特殊性质
1	n=2	$k\le1000$
2	$a_i$ 为等比数列	$k\le1000$
3	n=1	$k\le10^9$
4	n=2	$k\le10^9$
5	$a_i$ 为等比数列	$k \le 10 ^{12}$
6~10	无	$k \le 10 ^{12}$
11~12	a $_i>10^8$	$k\le10^{16}$
13~20	无	$k\le10^{16}$

在下列比赛中:

12月定时作业（基础算法）