T14 Make It One (CF1043F)

· · 个人记录

T14 Make It One (CF1043F)

CF传送门

洛谷传送门

题意简述
如果任意选择都不能满足条件，请输出 $−1$。 ##### 数据范围 $1 \leq n \leq 3*10^5 1 \leq a_i \leq 3*10^5
题解

思路

一眼看上去很简单的样子，却又想不到什么妙方法

特性很多，不如先来研究一下答案的特征？

2 \times 3 \times 5 \times 7 \times 11 \times 13 < 300000 < 2 \times 3 \times 5 \times 7 \times 11 \times 13 \times 17

答案最长只有7，因为只要不是无解，每加入一个数必定至少从gcd中去除一个质因数

最极限的情况：（转自ZEZ题解）

a[1]= 3*5*7*11*13*17 a[2]=2 * 5*7*11*13*17 a[3]=2*3 * 7*11*13*17 a[4]=2*3*5 * 11*13*17 a[5]=2*3*5*7 * 13*17 a[6]=2*3*5*7*11 * 17 a[7]=2*3*5*7*11*13

于是我们枚举答案为 len，判断是否满足

接下来怎么办呢？

一个很巧妙的想法：DP！

虽然只是要求我们判断是否有满足条件的解

但我们可以来计数（虽然看似多此一举，但方便转移）

设 dp[i] 表示选出 gcd 为 i 的方案数

最大公因数为 i 很不好处理，但有 i 这个因数就很好处理了

只需从能被i整除的数中选出 len 个即可

这其中还包含最大公因数不为 i 的，即都能被 i \times j 整除的

于是——

dp[i]=C^{len}_{cnt[i]}-\sum\limits_{j=2}dp[j]

其中 cnt[i] 表示 a[i] 中能被 i 整除的个数，可以预处理

显然是从大往小dp

当然我们总不能从无穷大开始吧，要从 gcd 最大可能值—— a[i] 最大值开始

只要 dp[1] 不是 0 ，就表示 len 可行

注意事项

所以要模一个大质数

比如 988244353 什么的

逆元直接打表噢

AC代码

#include<bits/stdc++.h>
using namespace std;
const long long N=300005,mod=998244353;
long long n,maxer=-1e9;
long long a[N],cnt[N],dp[N];
long long fx[8]={0,1,499122177,332748118,249561089,598946612,166374059,142606336};
long long C(long long m,long long n){
    if(m<n) return 0;
    long long ans=1;
    for(long long i=m;i>=m-n+1;i--) ans=ans*i%mod;
    ans=ans*fx[n]%mod;
    return ans;
}
int main(){
    scanf("%lld",&n);
    for(long long i=1;i<=n;i++){
        scanf("%lld",&a[i]);
        maxer=max(maxer,a[i]);
        for(long long j=1;j<=sqrt(a[i]);j++)//预处理cnt 
            if(a[i]%j==0){
                cnt[j]++;
                if(a[i]!=j*j) cnt[a[i]/j]++;
            }
    }
    for(long long len=1;len<=7;len++){//枚举答案 
        for(long long i=maxer;i>=1;i--){
            dp[i]=C(cnt[i],len);
            for(long long j=2;i*j<=maxer;j++)
                dp[i]=(dp[i]-dp[i*j])%mod;//枚举转移 
        }
        if(dp[1]) {printf("%lld",len);return 0;}//如果有解就输出 
    }
    printf("-1");
}