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

基础数论

本文同时作为在炼石计划 NOIP 2025 阶段的讲稿。

目录
  • 欧几里得算法
    • P11846
    • P9193
  • 扩展欧几里得算法
    • P5179
  • 类欧几里得算法
    • P5172
  • 万能欧几里得算法
    • CF868G
  • SB 树
    • AT_agc051_f

欧几里得算法

P11846

初始时给定两个整数 \(a,b\),在一次操作内可以将一个数加上另外一个数,给定 \(c,d\),求最少操作次数使得 \(a=c,b=d\) 或输出无解。

\(\texttt{Data Range:}\;Q\le 10^5,|a|,|b|,|c|,|d|\le 10^{18}\)

P9193

考虑如下代码:

string gen_string(int64_t a, int64_t b) {string res;int ia = 0, ib = 0;while (ia + ib < a + b) {if ((__int128)ia * b <= (__int128)ib * a) {res += '0';ia++;} else {res += '1';ib++;}}return res;
}

定义一个字符串是好的当且仅当其能被一组 \(a,b\) 生成,给定 \(a,b\),求它们对应的字符串中好的字符串的前缀数量。

\(\texttt{Data Range:}\;T\le 10,a,b\le 10^{18}\)

扩展欧几里得算法

P5179

求最简分数 \(\dfrac{p}{q}\) 满足 \(\dfrac{a}{b}<\dfrac{p}{q}<\dfrac{c}{d}\),在此基础上最小化 \(q\),然后再最小化 \(p\)

\(\texttt{Data Range:}\;T\le 500,a,b\le 10^9\)

类欧几里得算法

P5172

给定 \(d,r\),求 \(\sum\limits_{d=1}^{n}(-1)^{\left\lfloor d\sqrt{r}\right\rfloor}\)
\(\texttt{Data Range:}\;t\le 10^4,n\le 10^9,r\le 10^4\)

万能欧几里得算法

CF868G

\(n\) 个洞穴,有一个洞穴有宝藏。每一天选取 \(k\) 个洞穴挖掘,如果选中了宝藏所在洞穴则以 \(\dfrac{1}{2}\) 概率结束。求最优策略下期望结束天数。

\(\texttt{Data Range:}\;T\le 1000,n,k\le 5\times10^8\)

SB 树

AT_agc051_f

有两个沙漏,一个计时 \(1\) 秒,一个计时 \(\sqrt{2}\) 秒,\(Q\) 次询问能否计量出 \(x_i+y_i\sqrt{2}\) 秒。
\(\texttt{Data Range:}\;Q\le 10^5,|x_i|,|y_i|10^9\)

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

相关文章:

  • 第一次个人编程作业-论文查重
  • 使用Claude代码子代理生成项目特定提交消息的技术实践
  • 走迷宫(BFS)
  • MyBatis分页的原理和分页插件的原理是什么
  • 达成度报告
  • 旋转图像-leetcode
  • 【ChipIntelli 系列】ASR部分——合成语言模型和多网络(多语种)切换
  • 内网环境怎么安装软件(用 yum / apt 下载离线包并搬入内网)
  • tanh函数
  • P13617 [ICPC 2024 APC] Bit Counting Sequence
  • 打一局吗(60pts 解法)
  • 软工9.23
  • 本地部署qwen-0.6b
  • 25分钟小练习
  • 第七章 手写数字识别V2
  • 常用软件下载
  • 实用指南:S 4.1深度学习--自然语言处理NLP--理论
  • PyTorch图神经网络(五)
  • java
  • Jordan块新解
  • [CSP-S 2024] 染色
  • Kerberos 安装和使用
  • 第一次个人编程任务
  • 概率期望总结
  • redis实现秒杀下单的业务逻辑
  • 关于边缘网络+数据库(1)边缘网络数据库模式及选型
  • 题解:B4357 [GESP202506 二级] 幂和数
  • 2025年9月23日 - 20243867孙堃2405
  • 2025.9.23