这题是让我们找到a=∏ai，即a为ai的积和，让我们找出a的因子个数；
最终只需求出每个质因子的指数即可，我们可以使用一个map，记录每个质因子对应的指数。
- 我们对数字进行分类，合法的有p2p2,p4p4,p3p3,pqpq
- 前三种很好处理，现在考虑pqpq这种类型,如果a[i]=pqa[i]=pq那我们将所有数字都与a[i]a[i]求一次gcd，如果gcd(a[i],a[j])=pgcd(a[i],a[j])=p，那么可以直接更新map了。否则的话,质因子p,qp,q只在值为a[i]a[i]的数字中出现，我们统计一下这样的a[i]a[i]个数就好了。
接下来是代码：
#include<bits/stdc++.h> #define maxn 110000 #define rep(i,a,b) for(int i=a;i<b;i++) using namespace std; #define ll long long int gi() { int x = 0; char c = getchar(); while (c < '0' || c > '9') c = getchar(); while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar(); return x; } #define mod 998244353 //123****123 map<ll, int>test; ll a[maxn]; ll gcd(ll a, ll b) { return !b ? a : gcd(b, a % b);//本代码的核心，gcd约分代码 } int main() { int n; cin >> n; for (int i = 1; i <= n; i++) { cin >> a[i]; } for (int i = 1; i <= n; i++) { ll p = sqrt(a[i]); if (p * p == a[i]) { ll tmp = sqrt(p); if (pow(tmp, 4) == a[i]) { test[tmp] += 4; } else { test[p] += 2; } continue; } p = cbrtl(a[i]); if (pow(p, 3) == a[i]) { test[p] += 3; continue; } bool lazy = false; for (int j = 1; j <= n&&!lazy; j++) { if (a[i] != a[j]) { ll g = gcd(a[i], a[j]); if (g != 1) { test[g]++; test[a[i] / g]++; lazy = true; break; } } } if (!lazy) { test[a[i]] = sqrt(test[a[i]] + 1) + 1; test[a[i]] = test[a[i]] * test[a[i]] - 1; } } ll sum = 1; for (auto i : test) { sum = sum * (i.second + 1) % mod; } cout << sum << endl; }
题目大意：
给你两个数
1、给出两个大数a和b，要求计算(a&b) + (a & (b >> 1)) + (a & (b >> 2)) + ...
2、答案累加上一个操作的值
然后最终答案并且取摸998244353
题解：
因为第一个二进制不动，第二个在动，所以预处理第一个数获得答案，因为是and（与），所以只有2个都为1是才有贡献，例如样例：
1001
11010，
就会产生以下几种情况：
01001
11010
1001
1101
1001
0011
1001
0110
1001
0001
我们会发现，第一位的1分别和上面的第一个1和最后一个1异或起来对答案有贡献
所以这个1对答案的贡献是8+1=9
我们把这个规律推广开来
对y中每一个1进行如上操作
即可得出答案
但是，我们会发现答案复杂度是O（n×m）的，过不了
所以我们要预处理
用前缀和跑一遍x即可
复杂度优化到O；
#include<assert.h> #include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<cmath> #include<map> //#include<bits/stdc++.h> #define maxn 210000 #define rep(i,a,b) for(int i=a;i<b;i++) using namespace std; #define ll long long int gi() { int x = 0; char c = getchar(); while (c < '0' || c > '9') c = getchar(); while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar(); return x; } #define mod 998244353 //123****123 map<ll, int>test; ll gcd(ll a, ll b) { return !b ? a : gcd(b, a % b);//本代码的核心，gcd约分代码 } char a[maxn], b[maxn]; int sum[maxn]; int main() { int n, m; while (cin >> n >> m) { for (int i = n; i >= 1; i--) { cin >> a[i]; } for (int i = m; i >= 1; i--) { cin >> b[i]; sum[i] = sum[i + 1] + b[i] - '0'; } ll ans = 0, pw = 1; for (int i = 1; i <= n; i++) { if (a[i] == '1') { ans = (ans + (sum[i] * pw) % mod) % mod; } pw = pw * 2 % mod; } cout << ans << endl; } }
Codeforces 1043F(容斥+dp)
Problem:给n个数(n<=3e5)，每个数<=3e5，选择最少的数，使得他们的gcd为1。输出这个最小子集的大小。
Idea:Idea:Idea:可以二分，或者直接枚举，因为2 * 3 * 5 * 7 * 11 * 13 * 17 > 3e5，每次选择会删去一个素数，所以答案不超过7。接着用莫比乌斯反演验证答案是否存在，g(x，len)表示集合大小为len，gcd为x的倍数的方案数，那么验证f(1, len)的方案数不为0即可。
代码一
#include<bits/stdc++.h> using namespace std; typedef long long LL; const int N = 3e5+10; const int MOD = 1e9+7; bool isn[N]; int mu[N], p[N]; LL inv[N], fac[N]; void init() { inv[1] = 1; for(int i = 2; i < N; ++i) inv[i] = MOD-(MOD/i*inv[MOD%i]%MOD); fac[0] = 1, inv[0] = 1; for(int i = 1; i < N; i++){ fac[i] = fac[i-1]*i%MOD; inv[i] = inv[i-1]*inv[i]%MOD; } int pnt = 0; isn[1] = 1; mu[1] = 1; for(int i = 2; i < N; i++) { if(!isn[i]) { p[pnt++] = i; mu[i] = -1; } for(int j = 0; j<pnt && i*p[j]<N; j++) { isn[i*p[j]] = 1; if(i%p[j] == 0) { mu[i*p[j]] = 0; break; } mu[i*p[j]] = -mu[i]; } } } inline LL C(int a, int b) { return fac[a]*inv[b]%MOD*inv[a-b]%MOD; } int cnt[N]; int main() { init(); int n, g; scanf("%d", &n); for(int i = 1; i <= n; i++) { int x; scanf("%d", &x); if(i == 1) g = x; else g = __gcd(g, x); cnt[x]++; } if(g != 1) { puts("-1"); exit(0); } for(int i = 1; i < N; i++) for(int j = i+i; j < N; j += i) cnt[i] += cnt[j]; for(int i = 1; i <= min(n, 7); i++) { LL sum = 0; for(int j = 1; j < N; j++) if(cnt[j] >= i) { (sum += mu[j]*C(cnt[j], i)) %= MOD; } if(sum) { printf("%d ", i); break; } } return 0; }
代码二
#include<bits/stdc++.h> using namespace std; long long n,m,i,j,ii,now,A,B,f[300001],a[300001],cnt1[300001],cnt2[300001]; long long gcd(long long n1,long long m1){ if(!m1)return n1; return gcd(m1,n1%m1); } int main(){ scanf("%lld",&n); for(i=1;i<=n;i++){ scanf("%lld",&a[i]); if(a[i]==1){ puts("1"); return 0; } cnt1[a[i]]=cnt2[a[i]]=1; } now=a[1]; for(i=2;i<=n;i++)now=gcd(now,a[i]); if(now>1){ puts("-1"); return 0; } for(i=2;i<=n;i++){ for(j=3e5;j;j--){ A=B=0; for(ii=j;ii<=3e5;ii+=j){ f[j]-=f[ii]; A+=cnt1[ii];B+=cnt2[ii]; } f[j]+=A*B; } for(j=1;j<=3e5;j++){ f[j]=min(1ll,f[j]); cnt2[j]=f[j]; } if(cnt2[1]>0){ printf("%lld",i); return 0; } } }