@数论个人总结二-个人总结

i207M · 2018-08-20 23:12:36 · 个人记录

(x,y)关于Ax+By+C=0的对称点

~~精度不要太高~~

使用1-100构造一个上升子序列个数为N的序列，L<=100

N很大。见代码；

ll n;
int s[500], hd = 250, tl = 249;
int dfs(ll x)
{
    if (x == 0) return 0;
    if (x == 1)
    {
        s[++tl] = 1;
        return 1;
    }
    if (x & 1)
    {
        int t = dfs(x >> 1);
        s[++tl] = t + 1;
        return t + 1;
    }
    else
    {
        int t = dfs(x - 1);
        s[--hd] = t + 1;
        return t + 1;
    }
}

求1-N阶乘的逆元

倒着来，先用费马小定理求出N!的逆元，然后倒着，乘N-1,N-2...

求N!的位数

现由斯特林公式可得：

lnN!=NlnN－N+0.5ln(2N×pi)

而10的7次方阶乘的位数等于：

log10(N!)取整后加1

log10(N!)=lnN!/ln(10)

或者：

求组合数的后...位

将阶乘的每一位分解质因数，指数加加减减，最后一边高精，可以避免除法；

秦九昭公式-快速计算高次多项式

对于多项式方程f(x)，有f(x+p)=f(x)Modp，所以“解方程”这道题，只需要计算1-Mod-1的值即可；

整数分解为2的幂

任何正整数都能分解成2的幂，给定整数N，求N的此类划分方法的数量！比如N = 7时，共有6种划分方法。

7=1+1+1+1+1+1+1
  =1+1+1+1+1+2
  =1+1+1+2+2
  =1+2+2+2
  =1+1+1+4
  =1+2+4

显然要DP做；而我们为了防止算重，要人为规定顺序，比如规定升序排列；

设f[i][j]表示组成的数是i，方案中最大的数是2^j的方案数。

f[i][j]=\sum_{k=0}^j f[i-2^j][k]

配合前缀和可以O(nlogn)

优化：

f[i]=f[i-1]+f[i/2]×[i==0 \mod 2]

分情况：f[i-1]转移到f[i]表示加入了一个1，f[i/2]则表示f[i/2]的分解方案中，全部数乘2。这样转移也保证了加进来数的顺序是从大到小的，故不会重复。

O(n)

再优化：

性质：

对于一个数n，假设它二进制下有m个1，分别是第a1,a2…am位。对于n的任意一种分解方案，把所有2的幂升序排序，然后可以划分成m段，其中第i段的和是2^{ai}
对于一个数2^i的一种划分方案，如果不是只有它本身一个数，一定可以把这些2的幂升序排序，然后分成两段，每一段的和都是2^{i-1}

设g[i][j]表示做完了前i段（即n二进制下的前i个1位），最大的数是2^j的方案数。

再设一个辅助数组f[i][j]，表示组成2^i，最大的数是2^j的方案数。

f[i][j]=f[i-1][k]+f[i-k-1][j-k],k=[0,j]

g[i][j]=g[i-1][k]+f[i-k][j-k],k=[0,j]

高精进制转化的新思路：试除法

比如十进制转换为二进制：依次与2^p从大到小比较大小，大于2^p就减去并置一；%%%qyq

2-SAT解GCD与LCM方程

Hankson

每次交换相邻两数，最少几步使一个乱序数列达到有序

等于原序列的逆序对数；这样考虑：每次交换都会减少一个逆序对；

排序不等式

设有两组数a1,a2,……an和b1,b2,……bn，满足a1≤a2≤……≤an,b1≤b2≤……≤bn，c1,c2,……cn是b1,b2,……bn的乱序排列，则有a1bn+a2bn-1+……+anb1≤a1c1+a2c2+……+ancn≤a1b1+a2b2+anbn,当且仅当a1=a2=……=an或b1=b2=……=bn时等号成立。一般为了便于记忆，常记为：反序和≤乱序和≤顺序和.

高精GCD-辗转相减

0^0?=1 有时成立

求一个数的约数和

sum = [1+p1+p1^2+...+p1^{k1}] * [1+p2+p2^2+...+p2^{k2}] *...* [1+pn+pn^2+...+pn^{kn}].

等比数列求和可以使用递归进行；

没有逆元的剩余系除法

a/b \mod c==(a \mod b×c) / b

前提是保证整除；

这样做保证取余后的数字是b的倍数；

N×M数码问题的有解判断

有解指能够变成左上到右下1~NM-1，特殊情况可以建立映射；

将N×M的数字（除了空位）从上到下从左到右写成一行；

我们横向移动空白位置，序列不变；上下移动空白位置，相当于把一个数向前移动M-1格；

网格奇偶性指序列的逆序对数；

把x前移n-1次。若这m-1个数里，有a个比x小，b个比x大（不可能等于，且满足a+b = m-1），那么，初状态逆序对为b，末状态为a，相当于总体增加了a-b（若a<b则表明是减少）。

于是我们展开讨论，若m为偶数，那么m-1为奇数，所以a，b奇偶性不同\rightarrowa - b为奇数\rightarrow网格奇偶性改变。宏观来看，假设0位置一开始处于第i行，根据规则，0最后要处于第n行，总位移为n-i。即是要n-i次改变奇偶性。

n为奇数时较容易，因a，b同奇偶，则初状态逆序对数只要为偶数即可；

只要网格奇偶性相同，就可以互相转化

P2606 [ZJOI2010]排列计数

称一个1,2,...,N的排列P1,P2...,Pn是Magic的，当且仅当2<=i<=N时，Pi>Pi/2. 计算1，2，...N的排列中有多少是Magic的，答案可能很大，只能输出模P以后的值

实质：求1到n的所有排列中，满足小根堆性质的排列的个数。

对于转移，首先计算出i个节点的完全二叉树中，根节点的左子树包含的节点数l，右子树包含的节点数r。

首先，根节点的值必须为最小值。再考虑剩下的i-1个节点。很容易想到，可以在这i-1个节点中选出l个节点作为左子树，剩下的r个节点作为右子树。所以得出转移：

f[i]=C_{i-1}^l*f[l]*f[r]

中缀表达式转后缀表达式

建立一个栈：

1.遇到一个数，输出

2.遇到左括号，入栈

3.遇到右括号，不断取出堆顶并输出，直到栈顶为左括号，然后左括号出栈

4.遇到运算符，只要栈顶的符号的优先级不小于新符号，就不停的取出栈顶并输出，然后把新符号入栈；优先级：乘除>加减>左括号

计算阶乘位数

最好的方法：斯特林公式；

不好的方法：\sum \log(i)[i=1 \rightarrow n]

丑数

对于一给定的素数集合 S = {p1, p2, ..., pK},考虑一个正整数集合，该集合中任一元素的质因数全部属于S。这个正整数集合包括，p1、p1×p2、p1×p1、p1×p2×p3...(还有其它)。该集合被称为S集合的“丑数集合”。注意：我们认为1不是一个丑数。你的工作是对于输入的集合S去寻找“丑数集合”中的第N个“丑数”。

Sol：

为了找第i个丑数，那么一定要比第i-1个丑数大，而且是最小的那一个，可以发现比i-1大的丑数一定是比i-1小的丑数乘某个质数得到的，鉴于质数的数量很少，而丑数的数量很大，我们枚举质数，然后枚举丑数，直到大于第i-1个丑数，记录一下，找到所有的符合条件的丑数以后，找出最小值（也可以在寻找的途中更新最小值），那么这个最小值就是第i个丑数。

    s[0] = 1;
    for(ri i = 1; i <= m; ++i)
    {
        int mn = INT_MAX;
        for(ri j = 1; j <= n; ++j)
        {
            while(a[j]*s[b[j]] <= s[i - 1]) ++b[j];
            mn = min(a[j] * s[b[j]], mn);
        }
        s[i] = mn;
    }

将数k划分为若干份，使得可以表示1-k的任意一个数，数字除了1之外不得重复

很容易想到二进制拆分；

但是剩下的数也是2的整次幂怎么办？向前找和它相同的数，一个++一个--，因为2,2和1,3在拼数中发挥的作用是相同的；

法二：

我们举个例子。比如我们要算的是10，怎么办呢。首先要想组成1，必须有1。然后，如果要组成的一个数能由一部分加上另一部分组成就会很好了，10可以分成1~5和6~10，6~10可以由1~5加5组成，所以要选5，接下来只要组成1~5就可以了。就把5除2，一直这样。这很像倍增。所以只要一直这样就可以了。

注意是向上取整；

lyd的数学芝士

对于一个足够大的整数N，不超过N的质数大约有N/ln(N)

1 \rightarrow n$中，与$n$互质的数的和为$n×\phi(n)/2

POJ 3696 The Luckiest number

给出一个正整数L(≤2,000,000,000)，要使正整数 \underbrace{888...8}_{K}能整除L，求最小的K，如果不存在这样的K则输出0。

首先，111...1;222...2;...这类的数都可以表示为x/9×(10^x-1)

也就是找到K，使8/9\times(10^K-1)=L\times p，因为L已经包含gcd(L,8)这些因子，所以p需要包含8/gcd(L,8)这些因子，所以可以将p写成p=8/\gcd(L,8)\times p_1，问题转化成了求同余方程10^K≡1(\mod m)的最小的正整数解。

欧拉定理推论

如果正整数a,n互质，则满足a^x \equiv 1 (\mod n) 的最小正整数解x_0是\phi(n)的约数；

证明可以使用反证法，见lyd P143

Calculate Σi^k (1 <= i <= n)

递推求法:

由于

那么对于所有的累加得到

进一步得到

可以看出这是一个递推式，如果我们记

那么得到如下递归式

递推出口是k==1

伯努利数法：

伯努利数满足B_0==1，

注意快速幂在底数==模数p，且指数对phi(p)取模后为0时会出锅，如果指数不为0，应该返回0！

孙子定理是求对mi的逆元

Matrix Power Series

Given a n × n matrix A and a positive integer k, find the sum S = A + A2 + A3 + … + Ak.

法一：就像对数字进行等比数列求和可以分治一样，我们等比矩阵求和也可以分治；

法二：分块矩阵乘法：矩阵的矩阵乘法

矩阵的费马小定理？？？

对于一些特殊矩阵成立，比如bzoj5118，noi2013矩阵游戏；不过具体的判定...对拍或者祈祷吧；

冒泡排序

注意循环次数最少都为1（要检查一边）

单向冒泡：

交换次数：逆序对数

循环次数：max（[1,i-1]中比a[i]大的个数）（因为每次循环只会有一个在ai之前比ai大的数交换到ai后面）

比较次数：循环次数×(n-1)

单向冒泡的实质：

大的数很快到序列尾，小的数只会向前移动一格

双向冒泡：

循环次数：max(原位置在[1,i]但排序后位置在[1,i]之外的数量)

实质：

对于每相邻两个位置i，i+1的分割点，每次循环会有一个排序后位置在i之前的数到前面，同时有一个应在i后面的数到i后面

快排+冒泡？这个博客

计算p/q在b进制下是否是有限小数

核心是，先约分分数，p=0的情况特判；然后，此题的充要条件是：q的质因数全部都是b的质因数，验证方法就是不断除去gcd，看能否把q除到1；这个题有一个很重要的优化：对于一个gcd，while循环除直到不能整除，这样快；

        in(p),in(q),in(b);
        if(p==0) 
        {
            puts("Finite");
            continue;
        }
        ri tmp=gcd(p,q);
        q/=tmp;
        while((tmp=gcd(b,q))!=1)
            while(q%tmp==0) q/=tmp;
        puts(q==1?"Finite":"Infinite");

整数拼接

左边的含义是把数字顺着写下来；

原因是：我们可以把每一位（？？？个数字）表示成10^k\times x的形式，前面10 == 1 \mod 9，得证；

所以数字其实不用连续，任何数字顺着写下来就行；

一个函数

若$a>0$，$f(x) \uparrow$；若$a<0$，$f(x) \downarrow$； ## CF449D 给出一个长度为n的序列$a_1,a_2...a_n$。求构造出一个序列$i_1 \le i_2 \le ... \le i_k(1\le{k}\le{n})$使得$a_{i_1}\&a_{i_2}\&...\&a_{i_k}=0$。求方案数模10^9+7。也就是从$\{a_i\}$里面选出一个非空子集使这些数按位与起来为0. 考虑容斥：设$g[i]$为&后至少有i个1的方案数，则$ans=g[0]-g[1]+g[2]...$，考虑如何求g：$f[i]$表示多少数&i=i，这样，$g[i]=\sum 2^{f[\text{二进制下有i个一}]}-1$（不能不选）； f数组的求法就是高维后缀和；