技能参数由集合S={a_1,...a_m}给定, 其中m<=12, 2<=ai<=1e5, 不存在ai 整除 aj, i!...输入
多样例, 第一行是样例数, 每个样例由2行构成, 第一行给定 m 和 n
第二行给定 m 个正整数
输出
答案(保证<=1e15)
样例输入
2
2 4
2 3
3 10
6 11 20...所以本题的核心在于给定 x,如何计算 [1,x] 内恰好能被S 中的一个元素整除的数的个数.
一般性的考虑,假设有一个 [1,.....,x] 内恰好能被S中一个元素整除的元素的个数是
其中组合数
,而注意,如果令
的话, 则
其中lcm表示最小公倍数,除法按照 5/2=2 这样来理解。...所以本题就破了,[1,x]内恰好能被S中一个数整除的元素的个数是
又注意到 |S| <=12, 比较小,所以必须联想到状压. 我们完全可以二进制枚举所有A.