1. 首页
  2. 代码宅, 容斥原理, 排列组合, 数学问题

【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

 

评分 0, 满分 5 星
0
0
看完收藏一下,下次也能找得到
上一篇:
:下一篇

发表评论

gravatar

*

沙发空缺中,还不快抢~