本文主要是介绍数论入门整理（updating），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
一、gcd lcm
基础中的基础，一般用来处理计算第一步什么的，分数化简之类。
LL gcd(LL a, LL b)
{ return b ? gcd(b, a % b) : a;
}
<pre name="code" class="cpp">LL lcm(LL a, LL b)
{LL c = gcd(a, b);return a / c * b;
}例题：
hrbust 1178
hdu 2028 Lowest Common Multiple Plus
二、exgcd
通常用于解二元一次方程，线性同余方程组，高次同余方程组（babystep_giantstep）。
中国剩余定理。
void exgcd(LL a, LL b, LL& d, LL& x, LL& y)//ax + by = d, d = gcd(a, b)
{ if (b == 0) { d = a; x = 1; y = 0; } else { exgcd(b, a % b, d, y, x); y -= x * (a / b); }
} 例题：
二元一次方程：
poj 1061 + poj 2115 + poj 2142
uva 10673 Play with Floor and Ceil
线性同余方程组：
poj 2891 Strange Way to Express Integers
hdu 1573
高次同余方程组：
poj 3243 poj 2417 hdu 2815
中国剩余定理：
poj 1006 Biorhythms
三、素数
也是第一步的处理。
例题：
hdu 2098 分拆素数和
poj 2689 Prime Distance 大素数
poj 1811 + poj 2429 （Miller_Rabin大素数测试 + Pollard_Rho大合数分解）
四、快速幂
普通快速幂和矩阵快速幂。
用于求比较大的数的幂次取模。
比较大小可以取对数。
例题：
快速幂：
uva 10006 Carmichael Numbers
poj 1995
矩阵快速幂：
poj 3233（矩阵快速幂）
hdu 3292 No more tricks, Mr Nanguo（矩阵快速幂解佩尔方程）
五、欧拉函数
小于一个数x且与x互素的数的个数，就是欧拉函数，保存在phi[x]中。
1.打表：
void phi_table()
{ for (int i = 2; i <= maxn; i++) phi[i] = 0; phi[1] = 1; for (int i = 2; i <= maxn; i++) { if (!phi[i]) { for (int j = i; j <= maxn; j += i) { if (!phi[j]) { phi[j] = j; } phi[j] = phi[j] / i * (i - 1); } } }
} int euler_phi(int n)
{ int m = sqrt(n + 0.5); int res = n; for (int i = 2; i <= m; i++) { if (n % i == 0) { res = res / i * (i - 1); while (n % i == 0) n /= i; } } if (1 < n) res = res / n * (n - 1); return res;
} 例题：
基础：
uva 10820 poj 2407 poj 1284 poj 2478 poj 3090
进阶：
poj 3696 + poj 3358
六、因子相关
因子和，因子个数和，积性函数。
例题：
uva 10791 Minimum Sum LCM（拆分素因子）
poj 1845 （因子和）
poj 2992 （因子个数和）
hdu 1452 （积性函数+因子和+乘法逆元）
poj 2480 （积性函数+素因子和）
七、fib与catalan
catalan：
h(n) = (4 * n - 2) / (n + 1) * h(n - 1)
经典的总结：http://www.cnblogs.com/wuyuegb2312/p/3016878.html
例题：
hdu 1023 Train Problem II
uva 10303 uva 991
fib：
通常的fib直接打个表或者乱搞一下。
但是fib有个扩展就是fib的矩阵形式，在要求fib比较大的情况下，直接用矩阵快速幂搞定。
⎡⎣⎢100111110⎤⎦⎥⎡⎣⎢Sn−1Fn−1Fn−2⎤⎦⎥=⎡⎣⎢SnFnFn−1⎤⎦⎥
例题：
uva 10229 （fib矩阵形式+矩阵快速幂）uva 10518 （fib(n)调用多少次）
八、概率论、组合数学
排列组合，贝叶斯公式、全概率公式。
例题：
uva 10105 uva 10910 uva 10943（排列组合C）
hdu 2048 and 2049（错排问题）
uva 19759 （Dp+概率）
uva 10900 （期望）
uva 10056（等比数列求和）
uva 11181（贝叶斯公式）
uva 10277 （概率论 + 暴力）
uva 10169 （概率+取小数点后0的位数）
九、java大数使用
uva 10183 uva 10519 uva 10516
十、数学问题+技巧
uva 10061 How many zero's and how many digits ?（不同进制阶乘末尾几个0）+poj 1401
uva 11121 Base -2 (负进制计算)
uva 128 Software CRC（进制转换）
uva 106 Fermat vs. Pythagoras（勾股数求法）
uva 11029 Leading and Trailing（求n^k的前几位和后几位 证明）
poj 1091 跳蚤（n元一次不定方程+斥容原理）
uva 11027（康拓展开求序列|编码解码）
uva 10491 （广义三门问题）
poj 1695 （莫比乌斯反演）
十一、组合数学学习
1.排列组合：
| Type | Sample | Order Counts? | Rep? | Numbers of ways |
| 无重组合 | 从n个球中取r个 | No | No | C（n，r） |
| 无重排列 | 从n个人中找r个排队 | Yes | No | P（n，r） |
| 可重组合 | 从n种水果中选r个拼果篮 | No | Yes | C（n + r - 1， r） |
| 可重排列 | n个字母组成的r位串 | Yes | Yes | n ^ r |
| 多重全排列 | r1个a，r2个b组成的n位串 | Yes | Yes | n! / (r1! r2!) |
这篇关于数论入门整理（updating）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
