数论个人总结-数学

i207M · 2018-04-29 18:27:59 · Personal

回文数判定

在回文数中，如果位数为偶数的话，那么这些回文数都可以被11整除，如1001、1221、345543都是11的倍数，所以回文数位数为偶数时，只有11为素数

欧拉定理

线性打表求log2

lg[i]=(i>>(lg[i-1]+1))?lg[i-1]+1:lg[i-1];

定理: 对于正整数 p , q 满足 gcd(p, q) = 1, 我们有 px + qy = n 无非负整数解的最大正整数 n 为 pq - p - q.

证明如下：

扩展欧几里得的应用

    dx = x - y, dm = n - m;
    if (dx % (g = gcd(dm, l))) {
        puts("Impossible");
        return 0;
    }
    dm /= g, l /= g;
    exgcd(dm, l, x, y);
    l = abs(l);
    x = ((x * dx / g % l) + l) % l;

以青蛙的约会为例；

我们要求出a(m−n)+bl=y−x的a的最小解；不保证y-x与gcd关系

为了方便，我们变形ax+by=c；

先判断有解：c|gcd(a,b)；

然后注意到，c可能是gcd的倍数，而扩展欧几里得只能求出答案是gcd的情况；

我们先两边同除gcd(a,b)得到a/gx+b/gy=c/g；这样我们就可以扩展欧几里得了；求出的解，注意到通解的的形式为a=a0+k(c/g)，注意到我们两边同时除以g之后，模数也变化，所以最终的答案要mod(c/g)

注意在大部分情况下，我们要保证模数非负才有意义；

注意数据的最小值

以荒岛猎人为例，此题给予了每个洞穴的编号，所以洞穴最少不能少于编号；

向量的叉积

$|a×b|=|a|×|b|-sin(A)$； **$|a×b|$的值就为以a，b为边构成平行四边形的面积；** 叉积的运用（凸包和极角排序会用用到）： **$a×b>0$ 则说明 b在a的左上方；** **$a×b<0$ 则说明b在a的右下方；** ## 组合数学考虑在坐标平面上行走，求出到达点$(n,m)$同时不经过直线$y=x$上方的方案数： $((n-m+1)/(n+1))*C(n+m,m)

求gcd与X的gcd

由于gcd的神奇性质，每次取gcd与另一个数的gcd，要么答案不变，要么答案至少缩小为1/2；

对于大数的位运算

最好开Long Long；

如果按位判断，最好直接设定最高位，比如1<<30，不要随着输入变化；

给出一个序列，求出一段区间，使 &的结果＋ |的结果最大

答案是最大的数×2：

1.w>x w在前面的位上有1但x没有，那么肯定不选x，因为&和损失的高位上的1,再怎么增加|和的后面位置的1都于事无补,那么这个时候选w优于选wx优于选x

2.w=x 显然这时选不选都没关系

快速分解质因数

如果我们要快速分解很多10^9范围内的数，与其枚举O(\sqrt{N})的所有数，不如先筛出10^6以内的所有质数，然后直接枚举质数，会快很多；（严格说只要枚举\sqrt{10^9}的质数就可以了）筛素数时可以用MB素性测试；

看到互质问题，想到分解质因数

计算这个，不必分子分母分开计算；观察到分母一定是2的倍数，且最终未化简答案的分母是2^N，直接令f[1][1]=2^n，转移，最后除以2^N即可，否则阶乘会爆long long；

一个数的所有因数

可以O(\sqrt{n})计算

枚举每个<\sqrt{n}的数，如果i是n的因数，那么n/i也是n的因数，这样就把>\sqrt{n}的因数也计算了；

如果一个数是平方数，那么这个因数会计算两遍，在分解时要注意！！！

一个数的因数个数的数量级很小，1亿内因数个数最多的数为73513440，只有768个因数；

数论问题，打表找不出规律，就尝试优化爆搜或者打完整的表

期望、概率题的一种考虑方式：计算每个点被选择的期望，加起来就是答案

数三角形

给定一个nxm的网格，请计算三点都在格点上的三角形共有多少个。下图为4x4的网格上的一个三角形。注意三角形的三点不能共线。

~~这道题我一上来想的是枚举斜率，然而这很困难~~

正解：答案等于：任意选的方案数-选同一行或同一列的方案数-在一条倾斜直线的方案数；

如何统计第三个？

枚举倾斜向量！！！

对于向量(i,j)，有(n-i)(m-j)×2种放置在网格中的方法（n，m相对于输入都＋1了）；

相当于我们强制选这个向量的两段，看他中间经过了多少个点，答案是gcd(i,j)-1，画图可以知道；

约瑟夫问题

令f[n]表示当有n个候选人时，最后当选者的编号（从0开始）。

f[1] = 0

f[n] = (f[n - 1] + K) mod n

错排问题

n个有序的元素应有n！种不同的排列。如若一个排列式的所有的元素都不在原来的位置上，则称这个排列为错排。任给一个n，求出1,2,……,n的错排个数Dn共有多少个。

递归关系式为：D(n)=(n-1)(D(n-1)+D(n-2)) D(1)=0,D(2)=1

可以得到:

错排公式为 f(n) = n![1-1/1!+1/2!-1/3!+……+(-1)^n×1/n!]

n 个不同元素的一个错排可由下述两个步骤完成：

第一步，“错排” 1 号元素（将 1 号元素排在第 2 至第 n 个位置之一），有 n - 1 种方法。

第二步，“错排”其余 n - 1 个元素，按如下顺序进行。视第一步的结果，若1号元素落在第 k 个位置，第二步就先把 k 号元素“错排”好， k 号元素的不同排法将导致两类不同的情况发生：

1、 k 号元素排在第1个位置，留下的 n - 2 个元素在与它们的编号集相等的位置集上“错排”，有 f(n -2) 种方法；

2、 k 号元素不排第 1 个位置，这时可将第 1 个位置“看成”第 k 个位置(也就是说本来准备放到k位置为元素，可以放到1位置中),于是形成（包括 k 号元素在内的） n - 1 个元素的“错排”，有 f(n - 1) 种方法。据加法原理，完成第二步共有 f(n - 2)+f(n - 1) 种方法。

根据乘法原理， n 个不同元素的错排种数 f(n) = (n-1)[f(n-2)+f(n-1)] (n>2)

看我的博文《不等式与概率》

求将n划分成若干个正整数，求这些正整数的lcm的个数

首先，由于正整数个数不好确定，考虑逆向思维，p1^a1×p2^a2×..×pm^am是否是n的一个可行答案；

当且仅当p1^a1+p2^a2+...+pm^am<=n，证明比较显然；

~~当时就卡在这一步了~~

怎么求上面所说的个数呢？

分组背包！！！

分块的应用

实现两个操作：

1：在集合 S 中加入一个数 X ,保证 X 在当前集合中不存在。

2：给定Y，在当前的集合中询问Xmod Y 的最小值。N≤100000， 1≤X,Y≤300000

考虑到询问的时间复杂度与Y的大小有关，为O(Max/Y)，当Y比较小时，用时会很长；

$Y>\sqrt{Max}$？查找大于$0,y,2y…$的最小数，更新答案，最多sqrt次； **分块的新应用：面向时间复杂度编程** ## 球与盒子 [链接](https://blog.csdn.net/Jaster_wisdom/article/details/78506831) ## 给定一个数列，操作：选出两个数x,y，合并成一个新数$2×\min(x,y)$，求任意次操作后得到的最大值 $Max<=10^7

容易想到一个贪心：每次从队列里，选出两个最小的数x,y；如果2x<=y，舍去这个x；否则，合并为新数；这是正确的；

而如何O(N)的完成呢？考虑到我们新合成的数字大小是递增的，我们可以新建一个队列维护合成的数；初始的序列如何排序？桶排！

求\Sigma \sigma(i)，其中\sigma(i)为i的因子个数

N<=10^14

如何求单独的\sigma(i)？分解i=p_1^{q_1}p_2^{q_2}...，\sigma(i)=(q_1+1)(q_2+1)...

回归正题，显然不能线性筛；[1,n] 里约数有 i 的个数是 \lfloor\frac ni\rfloor 所以 ans=\sum_{i=1}^n\lfloor\frac ni\rfloor；

然后我们发现有很多 \lfloor\frac ni\rfloor都是一样的对于这些一样的数我们每次算一次似乎很浪费时间

所以我们每次 i 跳到 \lfloor\frac nj\rfloor=\lfloor\frac ni\rfloor-1这样的 j 上对于中间一样的数一次性算掉

复杂度O(\sqrt{N})，不会证；

    for(int i=1,j;i<=n;i=j+1){
        j=n/(n/i);
        ans+=(n/i)*(j-i+1);
    }

[1,n]里，对于给定的k，满足x的的倍数的个数为k的最大的x为n/k；

Dilworth定理

Dilworth定理：对于一个偏序集，最少链划分等于最长反链长度。

Dilworth定理的对偶定理：对于一个偏序集，其最少反链划分数等于其最长链的长度。

也就是说把一个数列划分成最少的最长不升子序列的数目就等于这个数列的最长上升子序列的长度。反过来也成立

对于1个1～N的排列，如果其LIS长度为L，那么其LDS长度最小值就是ceil(N / L)。

why？根据Dilworth定理，LIS长度为L，划分成的LDS数量最少是L个，每个的最小长度自然就是ceil(N / L)；

皇后游戏

~~看我的另一篇博客吧，这个锅了~~

博客

\max(\max(x,y)+a,z)+b=\max(x+a+b,y+a+b,z+b)

\max(-a,-b)<\max(-c,-d)==\min(c,d)<min(a,b)

求出1-n的排列中，字典序最小的逆序对数为m的排列

显然逆序对越多，字典序越大；n个数最多的逆序对为n(n-1)/2；

从小到大加入数字i，如果不考虑数字i，剩下的数能组成的最多逆序对是否>=m，如果是，把i放在最前面；否则，i肯定不是第一个，我们要最小化剩下的字典序，我们要最小化剩下的逆序对，所以我们要把这个数放在最后；

    for(int i=1;i<=n;i++){
        ll t=(ll)(n-i)*(n-i-1)/2;
        if(t>=m)a[fst++]=i;//放头上
        else a[lst--]=i,m-=(lst-fst+1);//放最后
    }

圆排列

从n个不同元素中不重复地取出m（1≤m≤n）个元素在一个圆周上，叫做这n个不同元素的圆排列。如果一个m-圆排列旋转可以得到另一个m-圆排列，则认为这两个圆排列相同。

P_n^{m}/m=n!/((n-m)!×m)

特别的，对于n==m时，答案为(N-1)!

解释：对于每一个圆排列，有N种断开方式，对应N!种普通排列，所以答案就是N!/N

给定平面上N个点，求组成的三角形数

~~JZOI上这道题超级卡常~~

任意取的方案数-不合法的方案数

如何求出不合法的方案？对于每个点，求出编号比它大的点与它的斜率（防止重复枚举）（没有斜率特判），对于每个点的每个斜率，任选两条线段都是不合法的ans-=sz(sz-1)/2；

看成线段考虑

斐波那契数列求和

Catalan数

栈操作序列，合法括号序列，网格移动不超过对角线的方案数，放置1和-1使任意前缀和非负，多边形三角剖分……

公式:C(2n,n)/(n+1)=C(2n,n) - C(2n,n-1)

eg.2N个括号（N对）有多少个合法序列；

Catalan数的一个推广:

n个左括号,m个右括号,任意前缀中左括号不少于右括号的序列数

C(n+m,m)-C(n+m,m-1)