Primes（素数测试）
传送门：HDU 2161 - Primes
题目大意：
给你一个数，让你判断它是不是素数。
解题思路：
超级大水题，题目简单数据范围也小，随便一个素数筛子就过了，注意下这个题认为 $1$ 和 $2$ 不是素数就行了。
通过代码：12345678910111213141516171819202122232425262728#include <iostream>#include <cstring>using namespace std;const int N = 17000;bool isprime[N];int prime[N], nprime; // 下标从 1 开始void doprime(void){ nprime = 0; memset(isprime, true, sizeof(isprime)); isprime[1] = false; for (long long i = 2; i < N; ++i) if (isprime[i]) { prime[+ ...
Death to Binary?（斐波那契+模拟）
传送门：POJ 2116 - Death to Binary?
题目大意：
有两个数，这两个数以斐波那契基数的形式给出。对应的斐波那契序列以 $Fib[0]=1, Fib[1]=2$ 开始。比如题目描述中的例子，数字 $40$，用斐波那契基数表示，可以是 $1101001$，也可以是 $10001001$，这里以第一个为例来解释，类似二进制，只不过右数第 $k$ 位（$k$从 $0$ 开始）对应的不再是 $2^k$，而是 $Fib[k]$，因为 $40=Fib[6]+Fib[5]+Fib[3]+Fib[0]$，和二进制一样，某一位上有值的为 $1$，没有的为 $0$，所以 $40=1101001_{Fib}$。然后告诉你，每个数字用斐波那契基数表示时，有唯一的一种表示是不包含两个连续 $1$ 的，让你拿这种情况去计算。给你两个斐波那契基数表示的数（不一定是没有连续 $1$ 的形式），让你计算加法，最后也以斐波那契基数的表示形式输出结果。然后对输出的格式有一定的要求，并且输出的数还得是那种没有连续 $1$ 形式（我有一句MMP不知当讲不当讲）。
解题思路：
讲道理这个题很简单，但是做起来 ...
C Looooops（扩展欧几里得）
传送门：POJ 2115 - C Looooops
题目大意：
给你一个 $C$语言中的 $for$ 循环伪代码，如下：
12for (variable = A; variable != B; variable += C) statements;
varibale是变量名，所有数据的类型都是一个 $k$ 位的无符号整数，给你 $A,B,C,k$ 的值，问你要这个循环会执行多少次后退出。
解题思路：
我们知道在 $C$语言中，如果一个数超过了它的上界，那么会从下界重新开始，同样如果超过了下界也是一样会从上界重新开始。比如说，int类型的范围是 $[-2147483648,2147483647]$。有如下代码：
12int int_max = 2147483647;cout << int_max + 1 << endl;
输出如下：
1-2147483648
可以看出数值从上界超出后回到了下界，这样这道题就很好去算了，设循环会执行 $x$ 次，我们可以根据题意列出一个等式：$(A+Cx)\%2^k=B$变形一下成为我们需要的形式：$Cx+2^ky=B-A$这里 ...
Bi-shoe and Phi-shoe（欧拉函数+素数筛）
传送门：LightOJ 1370 - Bi-shoe and Phi-shoe
题目大意：有一些撑杆跳选手，每个人有一个幸运值。现在要给这些选手每人买一个竹竿，每个竹竿都有一个得分，分数是它的长度数值的欧拉函数值，比如竹竿长 $l$，那这个竹竿的得分就是 $\varphi(l)$，$\varphi(l)$ 是不大于 $l$ 的正整数中与 $l$ 互素的数的个数。不知道什么是欧拉函数的同学看下这里。要求是给每个人买的竹竿的得分要大于或等于这个人的幸运值，然后一个竹竿的价格在数值上等于它的长度，问你在满足前面要求的前提下，最少要花多少钱买竹竿。
解题思路：虽然这道题考察的是欧拉函数的性质，但并没有让你真的去算欧拉函数值。我们知道，一个数 $x$ 的欧拉函数值 $\varphi(x)$ 一定是小于 $x$ 的，反过来说，一个数的欧拉函数值为 $y$，那么这个数一定大于 $y$。这样对于每一个幸运值(假设为 $x$)，我们就可以从 $x+1$ 往后查找，第一个素数就是我们要的，因为一个素数的欧拉函数值就等于这个素数减一，所以从 $x+1$ 往后第一个素数就是欧拉函数值大于等于 $x$ 的最小的 ...
快速幂模m算法
当数据过大且需要取模的时候，快速幂便无法再满足需求了，我们这里介绍快速幂模 m 算法，通常使用 long long 数据类型。
代码实现：1. 整数快速幂模m算法计算 $a^n\%m$，函数 quick_mod() 返回计算结果。123456789101112long long quick_mod(long long a, long long n, long long m){ long long ans = 1; while (n) { if (n & 1) ans = (ans * a) % m; n >>= 1; a = a * a % m; } return ans;}
2. 矩阵快速幂模m算法设 $A$ 为 MAXN 阶方阵(只有方阵可以使用快速幂)，计算 $A^n\%m$，函数 mat_quick_mod() 返回计算结果矩阵。123456789101112131415161718192021222324252627282 ...
快速幂
快速幂是一种利用二分思想计算乘方的算法，可以达到 $O(log_2 n)$。使用时注意根据场景修改数据类型，当数据范围过大且需要取余时，请使用快速幂模m算法。
代码实现：1. 整数快速幂计算 $a^n$，函数 quick_pow() 返回计算结果。123456789101112int quick_pow(int a, int n){ int ans = 1; while (n) { if (n & 1) ans = ans * a; n >>= 1; a = a * a; } return ans;}
2. 矩阵快速幂设 $A$ 为 MAXN 阶方阵(只有方阵可以使用快速幂)，计算 $A^n$，函数 mat_quick_pow() 返回计算结果矩阵。12345678910111213141516171819202122232425262728293031const int MAXN = 10; // 方阵的阶+1typedef st ...
Crossing River（贪心）
传送门：POJ 1700 - Crossing River
题目大意：有 $n$ 个人要过一条河，但只有 $1$ 条最多同时载两个人的船，已知每个人的过河时间，两个人的过河时间取决于两个人中过河时间长的那一个。问最短需要多久可以让所有人都过河。
解题思路：我们按过河时间从短到长将所有人排序，设时间第 $i$ 短的人为 $pi$，过河时间为 $t_i$，所有人都过河了的最短时间为 $T{min}$。当 $n=1,2,3$ 时，$T{min}$ 分别为 $t_1,t_2,t_1+t_2+t_3$，现在我们来考虑 $n\geq 4$ 的情况。从待过河的人中选出 $4$ 人分为一组，假设待过河的还有 $n{wait}$ 人，那么这 $4$ 个人包括 $p1,p_2,p{n{wait}-1},p{n{wait}}$，也就是待过河的人中过河时间最短的、次短的、次长的、最长的。对于这 $4$ 个人，我们要实现一个结果，就是将 $p{n{wait}-1},p{n{wait}}$ 送到对岸，并且 $p_1,p_2$ 重新回到待过河的人中。重复此过程，直到待过河的人数为 $2$ 或 $3$。为了实现上述结 ...
素数测试
素数测试就是检查一个正整数是否是素数，这个操作还是很常用的，下面是几个常用的素数测试方法，一般需要的时候可以直接拿来当板子用的。
1. 埃拉托斯尼斯筛法基本素数判别法：正整数 $n$ 是素数，当且仅当它不能被任何一个小于 $\sqrt n$ 的素数整除。定理：如果 $n$ 是一个合数，那么 $n$ 一定有一个不超过 $\sqrt n$ 的素因子。推论：如果 $n$ 是一个合数，则 $n$ 必有小于等于 $\sqrt n$ 的素因子。
给定一个正整数 $n$，使用上述定理可以找到所有小于等于 $n$ 的素数，这种方法由古希腊数学家埃拉托斯尼斯提出，所以该方法称为埃拉托斯尼斯筛法。先将 $2$~$n$ 的数写在纸上，在 $2$ 的上面画一个圆圈，然后划去 $2$ 的其他倍数；第一个既没有画圈又没有被划去的数是 $3$，将它再画圈，再划去 $3$ 的其他倍数；现在既没有画圈又没有被划去的第一个数是 $5$，将它画圈，并划去 $5$ 的其他倍数。以此类推，一直到所有小于或等于 $n$ 的各数都画了圈或划去为止。这时，纸上画了圈的那些数正好就是小于 $n$ 的素数。
代码实现：函数 dop ...
最大公约数与最小公倍数
概念1.设 $a$ 和 $b$ 是两个不全为 $0$ 的整数，称 $a$ 与 $b$ 的公因子中最大的为 $a$ 与 $b$ 的最大公因子，或最大公约数，记作 $gcd(a,b)$。2.设 $a$ 和 $b$ 是两个非零整数，称 $a$ 与 $b$ 的最小的正公倍数为 $a$ 与 $b$ 的最小公倍数，记作 $lcm(a,b)$。
性质(1) 若 $a|m,b|m$，则 $lcm(a,b)|m$。(2) 若 $d|a,d|b$，则 $d|gcd(a,b)$。(3) $lcm(a,b)=\frac{ab}{gcd(a,b)}$。(4) 设 $m,a,b$ 是正整数，则 $lcm(ma,mb)=m\times lcm(a,b)$。(5) 若 $m$ 是非零整数 $a_1,a_2,\cdots,a_n$ 的公倍数，则 $lcm(a_1,a_2,\cdots,a_n)|m$。
我们可以使用欧几里得算法计算 $gcd(a,b)$，然后将其带入 $lcm(a,b)=\frac{ab}{gcd(a,b)}$ 即可求得 $lcm(a,b)$。
代码最大公约数函数定义1234int gcd(int a, ...
初等数论四大定理
在数论中，威尔逊定理、欧拉定理、孙子定理、费马小定理并称初等数论四大定理。
1. 威尔逊定理如果整数 $p$ 满足 $(p-1)!\equiv-1\pmod p$ ，则 $p$ 是素数，逆定理同样正确。但是由于阶乘增长非常快的，其结论对于实际操作意义不大。通俗点，当且仅当 $p$ 是素数，则 $(p-1)!+1$ 能被 $p$ 整除。
2. 欧拉定理在数论中，欧拉定理（也称费马-欧拉定理）是一个关于同余的性质。欧拉定理表明，若 $n,a$ 为正整数，且 $n,a$ 互质，则:$a^{\varphi(n)}\equiv 1\pmod n$，其中 $\varphi(n)$ 是欧拉函数：对于正整数 $n$，欧拉函数是不大于 $n$ 的正整数中与 $n$ 互质的数的数目。
3. 孙子定理孙子定理是中国古代求解一次同余式组（见同余）的方法，是数论中一个重要定理，又称中国剩余定理。一元线性同余方程组问题最早可见于中国南北朝时期（公元5世纪）的数学著作《孙子算经》卷下第二十六题，叫做“物不知数”问题，原文如下：有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二。问物几何？即，一个整数除以三余二 ...