当前位置: 首页 > news >正文

洛谷题单指南-进阶数论-CF757B Bashs Big Day

原题链接:https://www.luogu.com.cn/problem/CF757B

题意解读:从n个数中选最多的gcd不为1的数的数量。

解题思路:

gcd不为1,那么可以从素因子作为切入点,用埃氏筛素数的过程,去用每一个素数的倍数去原数组里去查找对应的数的个数之和

还要算上素数自身在原数组中的个数,就是该素数的所有倍数的个数,对每个素数的倍数个数取最大值即可

需要注意,如果每个数都是1,计算得到的个数将是0,需特判,只能选1个数。

100分代码:

#include <bits/stdc++.h>
using namespace std;const int N = 100005;
bool vis[N];
int s[N], maxs, h[N];
int n, ans;int main()
{cin >> n;for(int i = 1; i <= n; i++) cin >> s[i], h[s[i]]++, maxs = max(maxs, s[i]);for(int i = 2; i <= maxs; i++){if(!vis[i]){int cnt = h[i];for(int j = i + i; j <= maxs; j += i) {vis[j] = true;if(h[j]) cnt += h[j];}ans = max(ans, cnt);}}if(ans == 0) ans = 1; //1个都选不出来,说明所有数都是1cout << ans;return 0;
}

 

http://www.hskmm.com/?act=detail&tid=31542

相关文章:

  • 2025年超市选择攻略:揭秘合肥砂之船的卓越购物体验
  • OFGB 广告屏蔽工具!优化工具!一款专门为 Windows 11 系统设计的开源广告屏蔽工具
  • 通过springboot编写的医院管理系统
  • 一文讲通zk-SNARK 跨链证明的核心原理
  • LGP11993 [JOIST 2025] 迁移计划 学习笔记
  • 2025年陶瓷膜瑕疵检测厂家最新权威推荐榜:专业检测设备批发与精准识别技术深度解析
  • docekr自动更新脚本
  • C语言restrict关键字
  • 企业搜索与智能工作流集成技术解析
  • 2025年液压阀块厂家最新推荐排行榜,液压阀块加工,阀块零件机加工,液压阀加工,各种液压阀块专业制造商实力解析
  • 线程的状态对比:等待、驻留、监视
  • [论文阅读] AI + 软件工程(Debug)| 告别 “猜 bug”:TreeMind 用 LLM+MCTS 破解 Android 不完整报告复现难题 - 实践
  • 软件开发初学
  • 2025年振动电机厂家最新权威推荐榜:高频/防爆/低噪声/卧式/直流/节能/侧板式/三段式全系列深度解析与选购指南
  • 测试面试官亲述:打动我的不是技能,而是这种思维
  • 大数据分析之MySQL学习1
  • 2025年GEO(AI搜索优化)源头厂家终极口碑推荐榜
  • 2025年GEO(AI搜索优化)源头厂家Top10权威推荐榜
  • 10.15
  • 2025 年丝杆升降机厂家行业推荐榜:螺旋丝杆升降机/蜗杆丝杆升降机/蜗轮丝杆升降机/聚焦精准传动需求,德州德特机械设备有限公司成优选
  • 深度解读:2025中国太阳能板TOP10榜单背后的格局颠覆与逻辑
  • Docker - 部署Consul 新
  • 重新定义行业:2025年中国市场最值得关注的十大太阳能品牌
  • 2025年变位机厂家最新权威推荐榜:焊接变位机/防位移变位机/重型变位机,精准定位与高效协同技术解析
  • 使用TCL脚本快速创建Quartus工程
  • kv cache缓存
  • 为什么笔记本电脑突然变得很卡?固态硬盘突然变慢是什么原因?
  • 用 Uni-app 开发 C3 继续教育题库系统:静态资源导入、响应式交互与考试逻辑实现全解析
  • 2025年上海律师服务最新权威推荐榜:经侦律师,民事/刑事律师,经济/婚姻律师,法务律师,负债律师事务所专业解析
  • 2025 年永磁电机厂家推荐台州市台成机电,单相永磁电机,三相永磁电机,变频永磁电机,稀土永磁电机,直流永磁电机,无刷永磁电机,风机永磁电机,节能永磁电机,高效永磁电机公司推荐