UVA11426 GCD - Extreme (II) UVA11426 GCD - Extreme (II)这几天我看了 LRJ 的书看到了这一题，就把这道题写了，正好这道题挺不错的。 题目题目PDF 知识欧拉函数 定义： $\varphi(n)$ 为小于等于 $n$ 与 $n$ 互质的数的个数 它有一些有趣的性质： $\varphi(n)$ 是积性函数 ： 如果有 $\gcd(i,j) = 1$ 那么就有 $\varphi(i \times 算法 数论 筛法 题解 UVA
组合数 这几天的竞赛期末考试中遇到了组合数的题目，就是 NOIP2016 组合数问题 原题，正好现在数学学到了一点点排列组合，就来整理一下吧。 组合数就是从 $n$ 个不同元素中，抽取 $m$ 个元素的方案数。 组合数公式为： \dbinom{n}{m}= \dfrac{n!}{m! \times (n-m)!}通过杨辉三角可得到递推公式： $\dbinom{i}{j} = \dbinom{i-1}{j- 算法 数论 组合数
LCA问题 LCALCA 的问题是很经典的，我这一次就来讲解一下 LCA 的求法，就先从一道模板题入手吧 题目P3379 【模板】最近公共祖先（LCA） 输入格式第一行包含三个正整数 $N,M,S$ 分别表示树的结点个数、询问的个数和树根结点的序号。 接下来 $N-1$ 行每行包含两个正整数 $x, y$ 表示 $x$ 结点和 $y$ 结点之间有一条直接连接的边（数据保证可以构成树）。 接下来 $M$ 行每行 算法 LCA 树
CF1A Theatre Square 题目题目描述用 $a \times a$ 的石板覆盖 $n \times m$ 的长方形广场，允许石板覆盖的区域超出广场，不允许打破石板，石板的两侧应平行于广场两侧，要求覆盖完广场所需的石板数量最少是多少。 输入格式输入有三个数字 $n,m,a$ ($1≤n,m,a≤10^9$) 思路首先，我们看到是广场是长方形的，而石板是正方形的，很容易就想到可能会出现一中特殊情况：（广场的面积不足以铺一个石板 算法 简单题 CodeForces
P3383 【模板】线性筛素数 题目P3383 【模板】线性筛素数 题目描述如题，给定一个范围$n$，有$q$个询问，每次输出第$k$小的素数。 输入格式第一行包含两个正整数 $n,q$，分别表示查询的范围和查询的个数。 接下来$q$行每行一个正整数$k$，表示查询第$k$小的素数。 输出格式输出$q$行，每行一个正整数表示答案。 数据范围对于 $100\%$ 的数据，$n = 10^8,1≤q≤10^6$，保证查询的素数不 算法 数论 筛法 题解
P1029 [NOIP2001 普及组] 最大公约数和最小公倍数 题目题目描述输入两个正整数$x_0, y_0$，求出满足下列条件的$P, Q$的个数: $P,Q$ 是正整数。 要求 $P, Q$ 以 $x_0$为最大公约数，以$y_0$为最小公倍数。 试求：满足条件的所有可能的$P, Q$的个数。 输入格式一行两个正整数$x_0, y_0$。 输出格式一行一个数，表示求出满足条件的$P, Q$个数。 知识讲解这一题是关于最大公约数（gcd）和最 算法 LCM GCD 数论
最小生成树(模板) 题目这是个模板题链接:P3366 【模板】最小生成树 题目描述如题，给出一个无向图，求出最小生成树，如果该图不连通，则输出 orz。 输入格式第一行包含两个整数 $ N,M $ ，表示该图共有 $ N $ 个结点和 $ M $ 条无向边。接下来 $ M $ 行每行包含三个整数 $ X_i,Y_i,Z_i $ ,示有一条长度为 $ Z_i $ 的无向边连接结点 $ X_i,Y_i $。 输出格式如 算法 Kruskal 最小生成树 题解 图论
过河卒 过河卒本题链接：p1002 过河卒 题目描述棋盘上 $ A $ 点有一个过河卒，需要走到目标$ B $点。卒行走的规则：可以向下、或者向右。同时在棋盘上 $ C $ 点有一个对方的马，该马所在的点和所有跳跃一步可达的点称为对方马的控制点。因此称之为“马拦过河卒”。 棋盘用坐标表示，$ A $ 点 $ (0,0) $ 、$ B $ 点 $ (n,m) $ ，同样马的位置坐标是需要给出的。 现在要求你 算法 递推