烹饪 [容斥]

烹饪 [容斥]

烹 饪 烹饪 烹饪

题目描述见链接 .

正 解 部 分 \color{red}{正解部分} 正解部分

若 { b i } \{b_i\} {bi​} 中存在能够 凑出 1 1 1 的数字, 则可以凑出所有数字 .

于是考虑哪些数字可以凑出 1 1 1,
2 2 2 个数字 x , y x,y x,y, a x + b y = 1 ax + by = 1 ax+by=1 有解的前提是 g c d ( i , j ) = 1 gcd(i, j) = 1 gcd(i,j)=1, 推广到更多数字 ∑ k i a i = 1 \sum k_ia_i = 1 ∑ki​ai​=1 有解的前提是 g c d ( k i ) = 1 gcd(k_i)=1 gcd(ki​)=1.

于是 题目转化 为: 求出有多少种选数方法, 满足 g c d ( b 1 , b 2 . . . b m ) = 1 gcd(b_1, b_2...b_m)=1 gcd(b1​,b2​...bm​)=1 .

考虑 容斥, 设 F [ i ] F[i] F[i] 表示满足以 i i i 为 g c d gcd gcd 的选出序列的个数,
F [ i ] F[i] F[i] 初值 为 2 c n t i − 1 2^{cnt_i}-1 2cnti​−1, 减去所有 F [ k i , k ∈ Z ] F[ki, k \in Z] F[ki,k∈Z] 即可得到 g c d = i gcd = i gcd=i 的序列数, 最后 F [ 1 ] F[1] F[1] 即为答案 .

实 现 部 分 \color{red}{实现部分} 实现部分

#include<bits/stdc++.h>
#define reg registerint read(){char c;int s = 0, flag = 1;while((c=getchar()) && !isdigit(c))if(c == '-'){ flag = -1, c = getchar(); break ; }while(isdigit(c)) s = s*10 + c-'0', c = getchar();return s * flag;
}const int maxn = 3005;
const int mod = 998244353;int N;
int Max_v;
int A[maxn];
int F[maxn];
int pw[maxn];int main(){N = read(); pw[0] = 1;for(reg int i = 1; i < maxn; i ++) pw[i] = 2ll*pw[i-1] % mod;for(reg int i = 1; i <= N; i ++) A[i] = read(), Max_v = std::max(Max_v, A[i]);for(reg int i = Max_v; i >= 1; i --){int cnt = 0;for(reg int j = 1; j <= N; j ++) cnt += (A[j]%i == 0);F[i] = pw[cnt] - 1;for(reg int j = 2*i; j <= Max_v; j += i) F[i] -= F[j], F[i] = (F[i]%mod+mod)%mod;}printf("%d\n", F[1]);return 0;
}