【Gcd】

【问题描述】

给出n个正整数,放入数组a里。

问有多少组方案,使得我从n个数里取出一个子集,这个子集的gcd不为1,然后我再从剩下的数中取出一个数,把它放进刚刚取出的子集里,使得gcd为1;

输出方案数mod 1000000007

【输入格式】

第一行一个数n;

第二行n个数,表示a数组;

【输出格式】

输出一个数表示答案

【输入样例】

3

2 3 2

【输出样例】

5

【样例说明】

选2 加的数为3 这样的集合有2个

选3 加的数为2 这样的集合有2个

选2 2 加的数位3 这样的集合有1个

所以一共有2+2+1=5个

【数据范围】

对30%的输入数据:1≤n≤10;

对100%的输入数据:1≤n≤500000,2≤a中元素≤10000000

 

stdKonjac

stdKonjac

一只挣扎的蒟蒻ACMer

评论太激烈有些评论需要亲动动手指翻页

留下你的评论

*评论支持代码高亮<pre class="prettyprint linenums">代码</pre>

*