题目链接

题意:是否存在选择方案使所选的数gcd=1

思路:f[i][j]表示选i个数gcd=j的方案数,cnt[i]表示包含因子i的数的个数,则f[i][j]=C(cnt[j],i)-f[i][d],j|d,j<d.

 

 1 #include <bits/stdc++.h>
 2 #define DBG(x) cerr << #x << " = " << x << endl;
 3 const int maxn = 3e5+5;
 4 const int mod  = 1e9+7;
 5 using namespace std;
 6 typedef long long LL;
 7 
 8 int n,a[maxn];
 9 int tmp,cnt[maxn];
10 LL f[15][maxn];
11 LL inv[maxn],fac[maxn];
12 
13 LL qpow(LL a,LL b,LL p){
14     LL res=1;
15     while(b){
16         if(b&1)res=(res*a)%p;
17         a=(a*a)%p;
18         b>>=1;
19     }
20     return res%p;
21 }
22 
23 int C(int a,int b){
24     return ((((fac[a]*inv[b])%mod)*inv[a-b])%mod)%mod;
25 }
26 
27 void init(){
28     for(int i=1;i<maxn;i++)
29         for(int j=i+i;j<maxn;j+=i)cnt[i]+=cnt[j];
30     fac[0]=1;for(int i=1;i<=n;i++)fac[i]=(fac[i-1]*i)%mod;
31     inv[n]=qpow(fac[n],mod-2,mod);
32     for(int i=n;i>=1;i--)inv[i-1]=(inv[i]*1LL*i)%mod;
33 }
34 
35 int main(){
36     scanf("%d",&n);
37     for(int i=1;i<=n;i++){
38         scanf("%d",&a[i]);
39         cnt[a[i]]++;
40         f[1][a[i]]++;
41         tmp=((i == 1) ? a[i] : __gcd(tmp,a[i]));
42     }
43     if(tmp != 1){puts("-1");return 0;}
44     else{
45         init();
46         for(int i=1;i<=7;i++){
47             for(int j=maxn-1;j>=1;j--){
48                 f[i][j]=C(cnt[j],i);
49                 for(int k=j+j;k<maxn;k+=j)f[i][j]=(f[i][j]-f[i][k]+mod)%mod;
50             }
51             if(f[i][1] > 0){printf("%d\n",i);return 0;}
52         }
53     }
54 }

View Code

 

版权声明：本文为DuskOB原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
本文链接：https://www.cnblogs.com/DuskOB/p/10006757.html