基础数论结论总结

以下是一些基础性数论结论的简单复习, 和一些代码实现. 证明的坑慢慢补.

内容极其简单基础, 巨佬勿喷…

约数

算术基本定理的推论

设$latex N=\prod_{i=1}^{m}P_i^{c_i}$(唯一分解), 则

n的正约数共$$\prod_{i=1}^{m}(c_i+1)$$个.

n的所有正约数之和为$$\prod_{i=1}^{m}(\sum_{j=0}^{c_i}p_i^j)$$

[POJ1845]Sumdiv[约数,逆元]

质数

线性筛质数

每个合数只被他的最小质因子筛一次.

欧拉函数

$latex \varphi(n) $表示1~n中与n互质的数的个数.

$$\varphi(n)=n\times \prod_{p|n}(1-\frac{1}{p})=n\times \prod_{p|n}\div p\times(p-1)  (p\in Prime)$$ 后者防止做乘法时溢出.

注意: 非质数n的所有质因子一定小于$latex \sqrt{n}$.

求欧拉函数代码实现: [SDOI2008]仪仗队[欧拉函数]

同余

费马小定理

$$a^p\equiv a \pmod{p}(p\in Prime)$$

可用于求模质数下的逆元.

欧拉定理

若$latex gcd(a,n)=1$, 则$$a^{\varphi(n)}\equiv 1\pmod{n}$$

可用于求模意义下的幂. 推论1:

若$latex gcd(a,n)=1$, 则$$a^b\equiv a^{b \mod{\varphi(n)}}\pmod{n}$$

推论1中等式右边的指数%$latex \varphi(n)$实际上也限制了BSGS算法中指数的枚举范围为0~P-1

推论2: a, n不一定互质且$latex b>\varphi(n)$时, 有$$a^b\equiv a^{\varphi(n)+\varphi(n)}\pmod{n}$$

exgcd与线性同余方程

Bezout定理

对于$latex \forall a,b\in Z$, 有:

$$\exists x,y\in Z, ax+by=gcd(a,b)$$

推论: 方程$latex ax+by=c$有解仅当$latex gcd(a,b)|c$

线性同余方程求解

$latex ax\equiv b\pmod{m}$, 求$latex x$或给出无解.

问题等价于$latex ax-b$是$latex m$的倍数, 设为$latex -y$倍, 则问题转化为求解$latex ax+my=b$.

可以先求解$latex ax’+my’=gcd(a,m)$.

若不满足$latex gcd(a,m)|b$则无解, 否则答案之一是$latex x_0=x’*\frac{b}{gcd(a,m)}$, 通解是$latex x_0+k*m/gcd(a,m)(k\in Z)$.

乘法逆元

$latex ax\equiv 1\pmod{b}$, 则$latex x$为$latex a$在$latex \mod b$意义下的逆元. 常用来处理取模意义下的除法.

$latex gcd(a,b)=1$时可以通过解同余方程求.

$latex b\in Prime$时可以用费马小定理求, 直接$latex x\equiv a^{-1}\equiv a^{b-2}\pmod{b}$. 注意$latex b|a$时逆元不存在.

线性同余方程组

中国剩余定理

 

扩展中国剩余定理

 

矩阵乘法

设A是n*m的矩阵, B是m*p的矩阵, 则C=A*B是n*p的矩阵.

$$C_{i,j}=\sum_{k=1}^{m}A_{i,k}*B_{k,j}(1<=i<=n,1<=j<=p)$$

代码实现: [洛谷P1939]【模板】矩阵加速(数列)[矩阵加速递推]

高斯消元

通过高斯消元可解线性方程组, 复杂度$latex O(N^3)$. 思路主要是依次选取每行的$latex x_1\text{~}x_n$作为主元, 然后用加减消元法消掉其它行同一位置的系数变成0, 最后得到每行只有一个非零系数的方程组, 否则给出NoSolution.

线性基

线性基的操作是一种特殊的高斯消元, 只是把初等行列变换换成了异或运算, 其他操作类比一下. 把一堆数写成二进制然后高斯消元就得到了它们的线性基, 每个原来那些数所能表出的数线性基里面的数都能且仅能表出. 注意最低位设为第$latex 0$位.

不过这样得到的01矩阵还有一个特殊的性质就是第$latex i$行的最高位$latex 1$在第$latex i$列(类比阶梯型矩阵). 所以可以考虑另一种构造方法: 设线性基的第$latex i$行为$latex ba[i]$, 初始时都为$latex 0$, 每次插入一个数$latex x$都把这个数从高位到低位扫描, 如果第$latex i$位为$latex 1$且$latex ba[i]$为$latex 0$则直接$latex ba[i]=x$, 否则就$latex x=x XOR ba[i]$消去高位的$latex 1$以便后续插入.

查询最大值: 从$latex ba[1]$一路扫到$latex ba[n]$, 如果异或上当前扫到的数答案变大就异或入答案, 这个贪心策略基于高位贡献大于低位.

int n,base[64];
in void insert(int x)
{
    for(re int i=62;i>=0;--i)
    {
        if(!(x&(1ll<<i))) continue;//千万记得要把1强制转换成long long!!!不然1默认为int型, 会炸!!!
        if(!base[i]) {base[i]=x;break;}
        x^=base[i];
    }
}	
signed main()
{
    n=read();
    for(re int i=1;i<=n;++i) insert(read());
    int ans=0;
    for(re int i=62;i>=0;--i)
        if((ans^base[i])>ans) ans^=base[i];
    printf("%lld\n",ans);
    return 0;
}

查一个数$latex x$是否存在: 从高到低扫描$latex x$的每一位, 如果第$latex i$位为$latex 1$则$latex x=x XOR ba[i]$. 最后如果$latex x==0$则存在. 因为从高往低当某一位的$latex 1$第一次出现后就再不会出现这一位的$latex 1$了(性质).

查询第$latex k$大的数: [HDU3949]XOR[线性基]

0/1分数规划

用于解决从n个二元组$latex (a_i,b_i)$中选一些数, 最大化$latex \frac{\sum a}{\sum b}$.

$latex \text{设}ans=\sum{a_i}/\sum{b_i}$

$latex \text{则有}\sum{a_i}-ans*\sum{b_i}=0$

$latex \sum(a_i-ans*b_i)=0(*)$

然后就可以二分ans了. 因为如果ans过大,(*)式就会小于0; 反之会大于零. 所以每次chk选出所有大于0的$latex a_i-ans*b_i$使得ans最大化的同时尽可能合法.

代码实现: [HNOI2009]最小圈[0/1分数规划,SPFA]

赞(1)

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址