一.引言本文将对NTL开源库进行分析与学习。NTL:是一个高性能、可移植的C++库，为任意长度的整数提供数据结构和算法；用于整数和有限域上的向量、矩阵和多项式；以及任意精度的浮点运算。NTL为以下领域提供最先进且高质量的算法实现：任意长度整数运算和任意精度浮点运算；整数和有限域上的多项式算术，包括基本算术、多项式分解、不可约判定、最小多项式计算、迹线、范数等计算；格基归约，包括非常健壮和快速的Schnorr-Euchner,实现、块Korkin-Zolotarev归约，以及块Korkin-Zolotarev的新Schnorr-Horner剪枝启发式；整数、有限域和任意精度浮点数的基本线性代数。

目录今日知识点：基于涂色问题的组合数求所有数的最大公约数阶乘质因数分解哥德巴赫猜想越狱找朋友全部相同 方形tax                越狱监狱有n个房间，每个房间关一个犯人，有m种宗教，一个犯人信仰一种。如果相邻的房间犯人信仰同一种宗教就会越狱。问有多少种可能发生越狱输入23输出：6思路：直接反正做：把总情况数减去不会发生越狱的情况数。总情况数是m^n。不会发生越狱的情况数是m*(m-1)^(n-1)。因为只有第一个人可以随意信仰宗教，其余人只需要和上一个人的不同即可。反正就是高中学过的涂色问题#includeusingnamespacestd;typedeflonglongll;c

​​​​​​1900C-Anji'sBinaryTree        题意：凯克西奇一直被安吉冷落。通过一个共同的朋友，他发现安吉非常喜欢二叉树，于是决定解决她的问题，以引起她的注意。Anji给了Keksic一棵有n个顶点的二叉树。顶点1是根，没有父顶点。所有其他顶点都有一个父顶点。每个顶点最多可以有2个子顶点、一个左子顶点和一个右子顶点。对于每个顶点，安吉都会告诉凯西奇它的左子和右子的索引，或者告诉他它们不存在。此外，每个顶点上都有一个字母，即"U"、"L"或"R"。克克西奇从根开始下棋，他的每一步都是这样走的：如果当前顶点上的字母是"U"，他就移动到它的父顶点。如果它不存在，他就什么也不

给定两个正整数a,b(1L={x*y|1^是异或操作对于任意两个整数:A∈L，B∈R，我们将B格式化为n+1(n为b的十进制数)十进制数(在B前填0)，然后将Bunion到A的末尾，得到一个新的整数AB。计算所有生成的整数AB的总和(如果总和超过，则返回“summod1000000007”，mod表示模运算)注意:你的算法时间不超过3秒我的算法很简单:我们很容易得到集合R中的最大数，R中的元素是0,1,2,3...maxXor,(元素max(a,b)可能不在R)中，使用哈希表计算集L。但是当a=30，b=100000时算法消耗4秒。举个例子:a=2,b=4,soL={1*1,1*2,1

数论入门提到数论，可能很多人都感到很头疼，甚至很多时候遇到一些问题，看到成篇的证明都会感到恐惧，而且由于关于ACM方面的数论资料，网上资料都比较驳杂。有时候很容易出现知其然不知其所以然的情况。所以今天给大家介绍一些关于数论入门最基础的知识和算法，内容会尽量从0基础开始，所以内容会尽量详细。不过其中部分证明还是需要一些高中数学基础的。由于内容很多，我整理了一个目录，按顺序讲今天的内容.目录一.合数，质数，整除，互质，同余，取模等基础概念。二.欧几里得算法三.扩展欧几里得四.费马小定理五.欧拉函数六.欧拉降幂七.素数筛八.快速幂九.逆元的用处和几种简单求法十.中国剩余定理一.数论中的基础概念和符号

数论知识本文主要介绍整除、质数和合数、同余定理、模逆元素、欧几里得除法、欧拉函数、欧拉定理、费马小定理、中国剩余定理（孙子定理）。文章目录数论知识简介一、整除二、质数和合数三、同余定理模逆元素四、Euclid（欧几里得）除法可以利用辗转相除法求最大公因子六、欧拉（Euler）函数欧拉定理七、费马小定理八、中国剩余定理CRT总结简介最近学习了公钥算法，涉及了一些数论中的知识。对一些数论的基础知识做一下总结。gcd是最大公约数。lcm是最小公倍数。一、整除a,b是任意的两个整数，b不为0，存在整数q，使得a=qb。记作：b|a二、质数和合数除了平凡约数±1和±n之外，n没有其他的因数。则n是质数（

数论——中国剩余定理、扩展中国剩余定理中国剩余定理定义中国剩余定理（ChineseRemainderTheorem，CRT）求解如下形式的一元线性同余方程组（其中\(m\)两两互质）：$\left\{\begin{matrix}x\equiva_1\pmod{m_1}\\x\equiva_2\pmod{m_2}\\\dots\\x\equiva_k\pmod{m_k}\end{matrix}\right.$过程计算所有模数的积\(M=\prodm_i\)；对于第\(i\)个方程：计算：\(M_i=\dfrac{M}{m_i}\)；计算：\(v_i={M_i}^{-1}\pmod{m_i}\)（

数论——欧几里得算法、裴蜀定理、扩展欧几里得算法引入最大公约数最大公约数即为GreatestCommonDivisor，常缩写为gcd。一组整数的公约数，是指同时是这组数中每一个数的约数的数。\(\pm1\)是任意一组整数的公约数；一组整数的最大公约数，是指所有公约数里面最大的一个。特殊的，我们定义\(\gcd(a,0)=a\)。最小公倍数最小公倍数即为LeastCommonMultiple，常缩写为lcm。一组整数的公倍数，是指同时是这组数中每一个数的倍数的数。\(0\)是任意一组整数的公倍数；一组整数的最小公倍数（LeastCommonMultiple,LCM），是指所有正的公倍数里面，最

数论——卢卡斯定理、求组合数说明温馨提示：组合数一般较大，下面的示范代码均无视数据范围，如果爆int请自行开longlong或高精度处理。引入从\(n\)个不同元素中，任取\(m\)个元素组成一个集合，叫做从\(n\)个不同元素中取出\(m\)个元素的一个组合；从\(n\)个不同元素中取出\(m\leqn\)个元素的所有组合的个数，叫做从\(n\)个不同元素中取出\(m\)个元素的组合数，也被称为「二项式系数」。用符号\(\dbinom{n}{m}\)来表示，读作「\(n\)选\(m\)」；组合数计算公式：\(\dbinom{n}{m}=\dfrac{n!}{m!\,(n-m)!}\)特别地，

数论——欧拉函数、欧拉定理、费马小定理欧拉函数定义欧拉函数（Euler'stotientfunction），记为\(\varphi(n)\)，表示\(1\simn\)中与\(n\)互质的数的个数。也可以表示为：\(\varphi(n)=\sum\limits_{i=1}^n[\gcd(i,n)=1]\).例如：\(\varphi(1)=1\)，即\(\gcd(1,1)=1\)；\(\varphi(2)=1\)，即\(\gcd(1,2)=1\)；\(\varphi(3)=2\)，即\(\gcd(1,3)=1\)，\(\gcd(2,3)=1\)；\(\dots\)性质欧拉函数是积性函数；即如果\(