hdu4135-Co-prime & Codeforces 547C Mike and Foam (容斥原理)
2023-03-14 09:48:58 时间
hdu4135
求[L,R]范围内与N互质的数的个数。
分别求[1,L]和[1,R]和n互质的个数,求差。
利用容斥原理求解。
二进制枚举每一种质数的组合,奇加偶减。
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int N = 100005; int fac[N], cnt; void factor(int n) { cnt = 0; int limit = sqrt(n); for (int i = 2; i <= limit; ++i) { if (n % i == 0) fac[cnt++] = i; while (n % i == 0) n /= i; } if (n > 1) fac[cnt++] = n; } ll solve(ll x, int n) { //1~x中与n互质的数 ll ans = 0; ll val; int num; //printf("cnt=%d\n", cnt); int st = 1<<cnt; for (int i = 1; i < st; ++i) {// 枚举所有情况,奇加偶减 val = 1; num = 0; for (int j = 0; j < cnt; ++j) { if (i & (1<<j)) { val *= fac[j]; num++; } } //printf(">>%d %lld %d\n", i, val, num); if (num & 1) ans += x/val; else ans -= x/val; } return x - ans; } int main() { ll x, y; int n; int t, cas=0; cin >> t; while (t--) { cin >> x >> y >> n; cout << "Case #" << ++cas << ": "; factor(n); cout << solve(y,n) - solve(x-1,n) << endl; } return 0; }
Codeforces 547C Mike and Foam
差不多啦
求新加入的数和已经存在的数有多少是不互质的。
#include <iostream> #include <cstring> #include <cstdio> #include <cmath> using namespace std; const int N = 500005; int a[N], vis[N], fac[N], tfac[N]; int n, m, q, tot; void getfactor(int x, int fac[], int &cnt) { int limit = sqrt(x); cnt = 0; for (int i = 2; i <= limit; ++i) { if (x % i == 0) { fac[cnt++] = i; while (x % i == 0) x /= i; } } if (x > 1) fac[cnt++] = x; } int add(int x, int d) { int cnt; getfactor(x, tfac, cnt); int st = 1<<cnt; int ans = 0; for (int i = 1; i < st; ++i) { int num = 0; int tmp = 1; for (int j = 0; j < cnt; ++j) { if (i & (1<<j)) { num++; tmp *= tfac[j]; } } if (d == -1) fac[tmp]--; if (num & 1) ans += fac[tmp]; else ans -= fac[tmp]; if (d == 1) fac[tmp]++; } if (d == -1) return -tot+ans; else return tot-1-ans; } int main() { while (~scanf("%d%d", &n, &m)) { memset(vis, 0, sizeof vis); tot = 0; for (int i = 1; i <= n; ++i) scanf("%d", &a[i]); long long ans = 0 ,tmp; while (m--) { scanf("%d", &q); if (vis[q]) vis[q] = 0, tot--, tmp = add(a[q], -1); else vis[q] = 1, tot++, tmp = add(a[q], 1); ans += tmp; printf("%lld\n", ans); } } return 0; }
相关文章
- 在 Go 里用 CGO?这 7 个问题你要关注!
- 9款优秀的去中心化通讯软件 Matrix 的客户端
- 求职数据分析,项目经验该怎么写
- 在OKR中,我看到了数据驱动业务的未来
- 火山引擎云原生大数据在金融行业的实践
- OpenHarmony富设备移植指南(二)—从postmarketOS获取移植资源
- 《数据成熟度指数》报告:64%的企业领袖认为大多数员工“不懂数据”
- OpenHarmony 小型系统兼容性测试指南
- 肯睿中国(Cloudera):2023年企业数字战略三大趋势预测
- 适用于 Linux 的十大命令行游戏
- GNOME 截图工具的新旧截图方式
- System76 即将推出的 COSMIC 桌面正在酝酿大变化
- 2GB 内存 8GB 存储即可流畅运行,Windows 11 极致精简版系统 Tiny11 发布
- 迎接 ecode:一个即将推出的具有全新图形用户界面框架的现代、轻量级代码编辑器
- loongarch架构介绍(三)—地址翻译
- Go 语言怎么解决编译器错误“err is shadowed during return”?
- 敏捷:可能被开发人员遗忘的部分
- Denodo预测2023年数据管理和分析的未来
- 利用数据推动可持续发展
- 在 Vue3 中实现 React 原生 Hooks(useState、useEffect),深入理解 React Hooks 的