Codeforces 1043F Make It One（DP+组合数学）

Codeforces 1043F Make It One（DP+组合数学）

题目链接：F. Make It One

题意:

给定$n$个数$ai$，选取尽可能少的数，使得这些数的$gcd$为$1$，问最少要选取几个数，输出个数，若无法使$gcd$为$1$，输出$-1$.

数据范围：$1\le ai\le 300000,1\le n\le 300000$

题解：

题目分析： 首先我们选取的每个数都应当有至少一个质因子是之前已经选取的集合所不拥有的，否则我选取这个数将不能使得$gcd$产生变化，即毫无作用，因此每个数都至少包含一个不同的质因子，$ai\le 3e5$,那么我们选取的数应当小于等于$7$个(最小的$47$个质数相乘都大于$3e5$了)。
问题求解：我们考虑用$dp[i][j]$表示选取了$i$个数，当前$gcd$为$j$的方案数,用数组$num[i]$表示包含因子$i$的数的个数，令$dp[i][j]=C_{num[j]}^i$,但是我们发现这样写的话，因为$num[j]$存的是包含因子$j$的数的数量，可能会有重复，比如我当前枚举的$j=2$，但$num[2]$也统计了$4,6,8$就会导致选取的$i$个数的$gcd$可能为$j$的倍数，因此我们还需要枚举$j$的倍数$k$并减去所以$dp[i][k]$，这样就能避免$gcd$不为$j$的情况了，因此完整状态转移方程：
$dp[i][j]=C_{num[j]}^i-\sum dp[i][k]$,$(2\ast j\le k\le 3e5,j|k)$
代码以及注释：

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include 
#include
	#ifndef local
	#define endl '\n'
#endif */
#define mkp make_pair
using namespace std;
using std::bitset;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
const int inf=0x3f3f3f3f;
const ll MAXN=1e6+10;
const ll INF=1e18;
const ll N=3e5+100;
const ll mod=1e9+7;
const ll hash_p1=1610612741;
const ll hash_p2=805306457;
const ll hash_p3=402653189;
//-----------------------------------------------------------------------------------------------------------------*/
// ll head[MAXN],net[MAXN],to[MAXN],edge[MAXN]/*流量*/,cost[MAXN]//费用;
/* 
void add(ll u,ll v,ll w,ll s){
	to[++cnt]=v;net[cnt]=head[u];edge[cnt]=w;cost[cnt]=s;head[u]=cnt;
	to[++cnt]=u;net[cnt]=head[v];edge[cnt]=0;cost[cnt]=-s;head[v]=cnt;
}
struct elemt{
	int p,v;
};
-----------------------------------
求[1,MAXN]组合式和逆元 
ll mi(ll a,ll b){
	ll res=1;
	while(b){
		if(b%2){
			res=res*a%mod;
		}	
		a=a*a%mod;
		b/=2;
	}
	return res;
}
ll fac[MAXN+10],inv[MAXN+10];
void init(){
	fac[0]=1;inv[0]=1;
	for(ll i=1;i<=MAXN;i++){
		fac[i]=(fac[i-1]*i)%mod;
		inv[i]=mi(fac[i],mod-2);
	}
}
ll C(int m,int n){//组合式C(m,n); 
	if(!n){
		return 1;
	}
	if(mmp;
struct comp{
	public:
		bool operator()(elemt v1,elemt v2){
			return v1.v --小顶堆  less --大顶堆  
priority_queue,comp>q;

	set::iterator it=st.begin();
inline void rd(int &x) {//快读（不能关同步）
    x=0; char c=getchar();
    while(c>'9'||c<'0') c=getchar();
    while(c<='9'&&c>='0') x=(x<<3)+(x<<1)+c-'0',c=getchar();
}
*/
//emplace_back()  等于push_back(),但效率更高,传输pair时emplace_back(i,j)==push_back({i,j}) 
// vector>edge; 二维虚拟储存坐标 
//-----------------------------------------------------------------------------------------------------------------*/
//mt19937 rnd(time(0));//高质量随机化函数，直接调用rnd()即可
//mapmp[N]; 
//map::iterator it;//迭代器
//emplace_back() 
/*
int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};
*/
ll mi(ll a,ll b){
	ll res=1;
	while(b){
		if(b%2){
			res=res*a%mod;
		}	
		a=a*a%mod;
		b/=2;
	}
	return res;
}
ll fac[MAXN+10],inv[MAXN+10];
void init(){
	fac[0]=1;inv[0]=1;
	for(ll i=1;i<=MAXN;i++){
		fac[i]=(fac[i-1]*i)%mod;
		inv[i]=mi(fac[i],mod-2);
	}
}
ll C(int m,int n){//组合式C(m,n); 
	if(!n){
		return 1;
	}
	if(m<n){
		return 0;
	}
	return fac[m]*(inv[n]*inv[m-n]%mod)%mod;
}
int a[N];
int dp[10][N];//选了i个数，当前gcd为j的方案数
int num[N];//因子包含i的数的个数
int vis[N];//数i的数量
int main(){
/*cout<
/*cout<
	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);//同步流（与快读不兼容）
	int n;
	cin>>n;
	init();//预处理组合数
	int mx=0;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		vis[a[i]]++;
		mx=max(mx,a[i]);
	}
	for(int i=1;i<=mx;i++){//处理出num数组
		for(int j=i;j<=mx;j+=i){
			num[i]+=vis[j];
		}
	}
	for(int i=1;i<=7;i++){//7个质数乘积>3e5
		for(int j=mx;j>=1;j--){//枚举当前选的数
			dp[i][j]=C(num[j],i);//选出i个因子包含j的数
			for(int k=2*j;k<=mx;k+=j){//减去gcd不为j的情况
				dp[i][j]=(dp[i][j]-dp[i][k]+mod)%mod;
			}
		}
	}
	for(int i=1;i<=7;i++){
		if(dp[i][1]>0){
			cout<<i<<endl;
			return 0;
		}
	}
	cout<<-1<<endl;//无解情况
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174