cf1043F. Make It One(dp 容斥原理)
程序员文章站
2022-03-30 22:37:57
题意 "题目链接" 给出$n$个数,问最少选几个数,使他们的$gcd = 1$ Sol 好神仙啊qwq。 首先,如果答案存在,那么最多为$7$(因为前$7$个质数乘起来$ = 3e5$) 考虑dp,设$f[i][j]$表示选了$i$个数,他们$gcd = j$的方案数! 没错是方案数! 那么我们只要 ......
题意
给出\(n\)个数,问最少选几个数,使他们的\(gcd = 1\)
sol
好神仙啊qwq。
首先,如果答案存在,那么最多为\(7\)(因为前\(7\)个质数乘起来\(>= 3e5\))
考虑dp,设\(f[i][j]\)表示选了\(i\)个数,他们\(gcd = j\)的方案数!
没错是方案数!
那么我们只要最后考虑一下\(f[i][1]\)是否有解就行了
设\(cnt[i]\)表示有多少个\(a_i\)存在\(i\)这个约数
转移的时候\(f[i][j] = c_{cnt[i]}^i - f[i][j * k], k >= 2\)
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<map> #include<vector> #include<set> #include<queue> #include<cmath> #include<tr1/unordered_map> //#include<ext/pb_ds/assoc_container.hpp> //#include<ext/pb_ds/hash_policy.hpp> #define pair pair<int, int> #define mp(x, y) make_pair(x, y) #define fi first #define se second //#define int long long #define ll long long #define ull unsigned long long #define rg register #define pt(x) printf("%d ", x); //#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1<<22, stdin), p1 == p2) ? eof : *p1++) //char buf[(1 << 22)], *p1 = buf, *p2 = buf; //char obuf[1<<24], *o = obuf; //void print(int x) {if(x > 9) print(x / 10); *o++ = x % 10 + '0';} //#define os *o++ = ' '; using namespace std; //using namespace __gnu_pbds; const int maxn = 3e5 + 11, inf = 1e9 + 10, mod = 998244353, mx = 3e5; const double eps = 1e-9; inline int read() { char c = getchar(); int x = 0, f = 1; while(c < '0' || c > '9') {if(c == '-') f = -1;c = getchar();} while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar(); return x * f; } int n, a[maxn], f[12][maxn], cnt[maxn], fac[maxn], ifac[maxn]; int add(int x, int y) { if(x + y < 0) return x + y + mod; return x + y >= mod ? x + y - mod : x + y; } int mul(int x, int y) { return 1ll * x * y % mod; } int c(int n, int m) { if(n < m) return 0; return mul(fac[n], mul(ifac[m], ifac[n - m])); } int fp(int a, int p) { int base = 1; while(p) { if(p & 1) base = mul(base, a); a = mul(a, a); p >>= 1; } return base; } main() { n = read(); for(int i = 1; i <= n; i++) { a[i] = read(), cnt[a[i]]++, f[1][a[i]]++; if(a[i] == 1) {puts("1"); return 0;} } fac[0] = 1; for(int i = 1; i <= n; i++) fac[i] = mul(i, fac[i - 1]); ifac[n] = fp(fac[n], mod - 2); for(int i = n; i >= 1; i--) ifac[i - 1] = mul(i, ifac[i]); for(int i = 1; i <= mx; i++) for(int j = i + i; j <= mx; j += i) cnt[i] += cnt[j]; for(int i = 2; i <= 11; i++) { for(int j = mx; j >= 1; j--) { f[i][j] = c(cnt[j], i); for(int k = j + j; k <= mx; k += j) f[i][j] = add(f[i][j], -f[i][k]); } if(f[i][1] > 0) {printf("%d", i); return 0;} } puts("-1"); return 0; }
上一篇: 将博客搬至CSDN
下一篇: PHP也能干大事之PHP中的编码解码详解