题意
给你 n 个数, 求一个最小集合, 这个集合里面数的最大公因数等于 1
- 1<=n<=3e5
- 1<=a[i]<=3e5
思路
先考虑什么情况下满足集合中的最大公因数 = 1?
集合中的每个数没有共同的素因子, 即所有素因子并没有包含于选出集合的所有数中, 存在结论前 7 个素因子的乘积为 510510, 所以可以得出选出的集合大小最大为 7
定义 dp[i][j] 为, 集合大小为 i, 集合最大公因数 = j 的方案数
dp[i][j]= \(\begin{pmatrix} cnt[j] \\ i \\ \end{pmatrix}\) - \(\sum_{k=2}^{\infty}\)dp[i][j*k]
处理
逆元打表求组合数
log(3e5) 时间处理出每个数的倍数个数 cnt[i]
从后往前扫求 dp[i][j]
- #include<bits/stdc++.h>
- #define ll long long
- using namespace std;
- const int P =1e9+7;
- const int M =3e5+5;
- ll F[M],Finv[M],inv[M],dp[20][M],cnt[M];
- int n,x,i,j,k;
- void init(){
- F[1]=Finv[1]=inv[1]=Finv[0]=inv[0]=1;
- for(int i=2;i<M;i++)inv[i]=inv[P%i]*(P-P/i)%P;
- for(int i=2;i<M;i++){
- Finv[i]=Finv[i-1]*inv[i]%P;
- F[i]=F[i-1]*i%P;
- }
- }
- ll C(int n,int m){
- if(m<0||n<m)return 0;
- if(m==0||n==m)return 1;
- return F[n]*Finv[n-m]%P*Finv[m]%P;
- }
- int main(){
- init();
- scanf("%d",&n);
- for(i=1;i<=n;i++){
- cin>>x;cnt[x]++;
- }
- for(i=1;i<M;i++)
- for(j=i+i;j<M;j+=i)
- cnt[i]+=cnt[j];
- for(i=1;i<=15;i++){
- for(j=M-1;j>=1;j--){
- dp[i][j]=C(cnt[j],i);
- for(k=j+j;k<M;k+=j){
- dp[i][j]=(dp[i][j]-dp[i][k]+P)%P;
- }
- }
- if(dp[i][1]>0){
- cout<<i;return 0;
- }
- }
- cout<<-1;
- }
来源: http://www.bubuko.com/infodetail-2827383.html