#P2429. 制杖题
制杖题
题目描述
求不大于 的、质因数集与给定质数集有交集的自然数之和。
输入格式
第一行,两个整数 。
第二行, 个整数,表示质数集内的元素 。
输出格式
一个整数,表示答案,对 取模。
2 15
3 5
60
提示
样例解释:所有符合条件的数为 ,其和为 。
测试点编号 | 规模 |
---|---|
, | |
, | |
, |
对于 的数据,,。
求不大于 m 的、质因数集与给定质数集有交集的自然数之和。
第一行,两个整数 n,m。
第二行,n 个整数,表示质数集内的元素 pi。
一个整数,表示答案,对 376544743 取模。
2 15
3 5
60
样例解释:所有符合条件的数为 3,5,6,9,10,12,15,其和为 60。
测试点编号 | 规模 |
---|---|
1∼3 | nm≤107 |
4∼5 | n≤2,m≤109 |
6∼7 | n≤20,m≤108 |
8∼10 | n≤20,m≤109 |
对于 100% 的数据,1≤n≤30,1≤m≤109。