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

P10364 [PA 2024] Dzielniki 题解

考虑倍增,现在已经知道答案 \(ans \bmod 2^k\) 的值,考虑求出 \(ans \bmod 2^{k+1}\) 的值。

\(x = ans \bmod 2^k\),则 \(ans \bmod 2^{k+1} = x\)\(ans \bmod 2^{k+1} = x + 2^k\)。两个都试一遍,如果 \(d(ans - x) \bmod (k+1) = 0\) 就可以认为他是 \(2^k\) 的倍数,如果有多个数满足条件就都保留下来,最后得到 \(ans \bmod 2^{64}\),就是答案(显然这样的数只会有一个)。

实际上状态数不会太多,询问可以记忆化,次数在 \(500\) 左右。

两个数先试哪个可以随一下,这样可能可以减少常数。

std::mt19937 mtrd(time(0));
int solve(ll x,int dep){if((1ll<<dep)>n){ans=(1ll<<dep)-x;return 1;}ll k=(1ll<<dep);int op=mtrd()%2;for(int t:{0^op,1^op}){if(Query(x+k*t)%(dep+1)==0)if(solve(x+k*(t^1),dep+1))return 1;}return 0;
}
http://www.hskmm.com/?act=detail&tid=22541

相关文章:

  • 20251001 之所思 - 人生如梦
  • 25普及联考day6爆炸记
  • unity面向组合开发一:面向对象(OOP)与面向组合(EC)
  • 两级页表
  • 复健。(10月,OI)
  • 实用指南:自动驾驶中的传感器技术55——USS(1)
  • 市场交易反心理特征之三:日内假反转
  • 实用指南:云服务器 + Jenkins 实现项目自动化部署与上线
  • Linux 中awk命令如何统计每行指定字符出现的次数
  • 常系数齐次微分方程
  • 变量
  • 具有快表的地址变换机构
  • 关于子集的枚举与高维前缀和
  • HyperWorks 14.0 轮毂仿真全流程详细教程
  • 原来的OJ怎么没了?
  • 【Linux】库的链接与加载 - 详解
  • CSP-S模拟26
  • 存在是必然的有机系统,好事多磨,心诚则灵
  • 2025 年陶土砖厂家权威推荐 TOP 品牌排行榜,劈开 / 红色 / 干挂 / 砌筑 / 仿古 / 透气 / 耐火 / 异型 / 装饰 / 外墙陶土砖产品厂家推荐
  • AGC015E Mr.Aoki Incubator
  • 2025 年臭氧发生器厂家 TOP 实力工厂推荐榜单排名,大中型 / 水处理 / 多功能臭氧发生器推荐这十家公司!
  • 2025 年采光瓦厂家 TOP 企业品牌推荐排行榜,详解数字化工厂与就近发货实力采光瓦推荐这十家公司!
  • 2025 年合成树脂瓦厂家 TOP 企业品牌推荐排行榜,防腐方案与定制能力全景对比合成树脂瓦公司推荐!
  • 2025 年人造草坪足球场厂家推荐 TOP10 品牌权威排行榜单,深度剖析人造草坪足球场行业优势公司
  • 2025 年望远镜厂家 TOP 企业品牌推荐排行榜,助你精准选购性价比高的望远镜推荐这十家公司!
  • Coze源码分析-资源库-删除数据库-后端源码-安全与错误处理 - 详解
  • 动手动脑实验性问题总结
  • 链表实现双端队列
  • FFmpeg和ZLMediaKit 实现本地视频推流
  • SQL 多表查询速查:JOIN、子查询一文全掌握 - 详解