#P2429. 制杖题

制杖题

题目描述

求不大于 mm 的、质因数集与给定质数集有交集的自然数之和。

输入格式

第一行,两个整数 n,mn, m

第二行,nn 个整数,表示质数集内的元素 pip_i

输出格式

一个整数,表示答案,对 376544743376544743 取模。

2 15
3 5
60

提示

样例解释:所有符合条件的数为 3,5,6,9,10,12,153,5,6,9,10,12,15,其和为 6060

测试点编号 规模
131 \sim 3 nm107n m \le {10}^7
454 \sim 5 n2n \le 2m109m \le {10}^9
676 \sim 7 n20n \le 20m108m \le {10}^8
8108 \sim 10 n20n \le 20m109m \le {10}^9

对于 100%100 \% 的数据,1n301 \le n \le 301m1091 \le m \le {10}^9