中国剩余定理 《孙子算经》有云： 今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二，问物几何？ 大意为：有 个物品，满足如下线性同余方程组： 刚入坑编程的估计在“循环结构”那一章里就写过求解这个方程的枚举代码了。这种方式不好的一点就是码量随方程数的增多而膨胀（但是你可以写一个生成计算代码的程序，然后运行编译后的程序）。我们急需一种通解，在码量不增的情况下实现对这个方程组的求解。 ...

欧拉函数 欧拉函数 ，表示 内与 互质的数的个数。对于质数 显然有 。特殊地，。欧拉函数是一个积性函数，对任意互质的数 ，都有 。不互质时，如果 为奇数，那么有 。 如果 可以用算术基本定理分解成 的形式，那么 。注意，若 可以被同一个质数反复除尽，即存在一个 和 使得 ，计算时同样只对这个质数计算一次贡献。 证明： 正难则反，考虑用 内的所有数的个数减去不互质的数的个数...

您已获得最佳的阅读体验！ 题目原型谜题解法浅究（ 的情况） 题目地址 本题考察模意义下的高斯消元。 基本思路是，让 号方块分别击打 次，使得最终每个方块都朝向位置 。 欲解决此题，首先需要为每个位置编号。定义 为“击打 方块后， 均会旋转一次”。那么样例输入 #1 如下图（编号方式不唯一），红线为目标方向、初始时均在 朝向： 假设三个方块需要击打 次，那么可以列出以下方程组：...

欧几里得算法 众所周知的是，欧几里得算法可以用来求解最大公约数。它的核心是一个恒等式 ，并且在 时函数值是 。C++14 标准提供一个函数 __gcd() 来求解最大公约数，而在 C++17 以后，我们可以使用 gcd() 和 lcm() 函数来求解两个数的最大公约数和最小公倍数。 通常我们采用递归版本： 123int gcd(int a, int b) { return b ? g...

基本定理 算术基本定理 任何一个合数均可被唯一分解成若干质数的乘积。 也就是说任何合数都可以唯一地表示成 的形式，这条定理在之后的质数筛中有大用。 素数定理 中的质数个数约等于 可以用来粗略估计在当前数据范围下质数的个数，以便更具有针对性的选用质数筛法。据说这个定理有一个非常初等的证明，仅涉及到极限、自然对数函数和指数函数的一些简单性质（子供向），非常适合初中生茶余饭后作为谈资...

数位DP 简介 数位DP是一种基于按位枚举的计数类DP。一般来说，当题目要求对所有符合特殊性质的数字计数（且这些性质可以转化到数位上讨论）、对给定区间内的合法数做统计、数据范围中出现了超大的上界时，就可以考虑使用数位DP来进行求解。 数位DP的时间复杂度基本上是 级别的，其中 为状态数，可以看作是记忆化搜索数组每一维上界的总乘积。因此在大多数情况下它能做得很好。 数位DP 基本实现 数位...

您已获得最佳的阅读体验！ 题目地址：P10503 假设我们有一个称为 233 矩阵。在第一行，它可能是 233、2333、23333...（表示 ，，...）。此外，在 233 矩阵中，我们有 。现在已知 ，你能告诉我 233 矩阵中的 吗？ 发现 很小、 很大，于是选择使用 的矩阵快速幂做法。 假设矩阵一开始存储 列的信息，它看起来是这样的： 由于涉及到 的计算，我们需要...

您已获得最佳的阅读体验！ 题目地址：P10938 题目难度：省选/NOI- Vani 和 cl2 在一片树林里捉迷藏。 这片树林里有 座房子， 条有向道路，组成了一张有向无环图。 树林里的树非常茂密，足以遮挡视线，但是沿着道路望去，却是视野开阔。 如果从房子 沿着路走下去能够到达 ，那么在 和 里的人是能够相互望见的。 现在 cl2 要在这 座房子里选择 座作为藏身点，同时 V...

您已获得最佳的阅读体验！ 题目地址：P10939 题目难度：提高+/省选- 给定一个 的棋盘，有一些格子禁止放棋子。 问棋盘上最多能放多少个不能互相攻击的骑士（国际象棋的“骑士”，类似于中国象棋的“马”，按照“日”字攻击，但没有中国象棋“别马腿”的规则）。 看到数据范围，，状压 DP 肯定是没戏的。转而寻找其他能够解决棋盘问题的算法。 棋盘是这样的（从隔壁 P3355 借的图）： ...

您已获得最佳的阅读体验！ 题目地址：P10935 题目难度：提高+/省选- 银河中的恒星浩如烟海，但是我们只关注那些最亮的恒星。 我们用一个正整数来表示恒星的亮度，数值越大则恒星就越亮，恒星的亮度最暗是 。 现在对于 颗我们关注的恒星，有 对亮度之间的相对关系已经判明。 你的任务就是求出这 颗恒星的亮度值总和至少有多大。 输入格式： 第一行给出两个整数 和 。 之后 行，每行三个...