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

您已获得最佳的阅读体验！ 题目原型谜题解法浅究（ 的情况） 题目地址 本题考察模意义下的高斯消元。 基本思路是，让 号方块分别击打 次，使得最终每个方块都朝向位置 。 欲解决此题，首先需要为每个位置编号。定义 为“击打 方块后， 均会旋转一次”。那么样例输入 #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 题目难度：提高+/省选- 银河中的恒星浩如烟海，但是我们只关注那些最亮的恒星。 我们用一个正整数来表示恒星的亮度，数值越大则恒星就越亮，恒星的亮度最暗是 。 现在对于 颗我们关注的恒星，有 对亮度之间的相对关系已经判明。 你的任务就是求出这 颗恒星的亮度值总和至少有多大。 输入格式： 第一行给出两个整数 和 。 之后 行，每行三个...

您已获得最佳的阅读体验！ 题目地址：P7812 题目难度：省选/NOI- 题目类型：提交答案  Special Judge 本题为提交答案题。 给你一个长为 的序列 ，定义 的排列 的权值为 你可以理解为这个排列是一个环，即 。 请构造一个权值尽量大的 的排列。 输入格式： 第一行一个整数 。 第二行 个整数表示序列 。 输出格式： 一行 个整数表示排列。 数据范围： 对于 ...