数论

---

刷题时遇到的一些数论知识，记录一下。

给圆上三点，求园的周长

三角形面积：\(S = \frac{1}{2}absinB\)

根据海伦公式：\(S = \sqrt{p(p-a)(p-b)(p-c)}\)

根据正弦定理：\(\frac{a}{sinA} = \frac{b}{sinB} = \frac{c}{sinC} = d\)

把\(sinA = \frac{a}{d}\)代入上式得：

$$d = \frac{abc}{2S}$$

外界圆周长： \( l = d*\pi\)

扩展欧几里得算法

贝祖定理：

如果a、b是整数，那么一定存在整数x、y使得ax+by=gcd(a,b)。

得到每两个相邻状态的x和y的转化，就可以在求gcd的同时对x和y进行求值：

\(a % b = a-(a/b)*b\) 代入：

\(bx1 + (a-(a/b)b)*y1\)

=ay1 + b(x1 – a/b*y1) = gcd

发现 \( x = y1 , y = x1 – a/b*y1\)

int exgcd(int a,int b,int &x,int &y)
{
    if(b==0)
    {
        x=1,y=0;
        return a;
    }
    int d=exgcd(b,a%b,x,y);
    int k=x;
    x=y;
    y=k-a/b*y;
    return d;
}

无限循环小数

万能公式

设小数\(0.abcdefef\)…, 设其对应最简分数为: \(\frac{x}{y}\)

设非循环节长度为c，循环节总长度为k，则

$\frac{x}{y}*10^{k+c} = abcdefef $ (将小数点后的数省略)

$\frac{x}{y}*10^{c} = abcd $ (将小数点后的数省略)

相减得到：

$\frac{x}{y} = \frac{abcdefef-abcd}{10^{c}*(10^k-1)}$

矩阵

Homogeneous矩阵——写在 n 个独立位置上的数的和相等。

判断一个矩阵是否是Homogeneous矩阵，通过局部递推出规律：

对于一个n×n方阵，只要它的所有（n-1)×(n-1)子方阵是Homogeneous的，则该方阵是Homogeneous的；进一步递推可得，只要该方阵的所有2×2的子方阵符合两对角线相加相等，则该方阵是Homogeneous的。

最大子矩阵

将二维数组转化为一维数组，再求最大子序列和。

（1）第一轮：第一次仅第一行合并；第二次1、2行合并；第三次1、2、3行合并…

（2）第二轮：第一次仅第二行合并；第二次2、3行合并；第三次2、3、4行合并…

（3）第三轮：第一次仅第三行合并；第二次3、4行合并；第三次3、4、5行合并…

求最大子序列：

初始化ans=0，累加0到n-1个元素，每一步得到一个sum，如果某一步中sum>ans，则更新ans，如果sum<0，则重置sum为0，最终ans中储存的即为最大子序列和。

素数和

哥德巴赫猜想： 每个大于4的偶数可以写成两个奇素数的和。

将每个数表示成4个素数的和：

N<8 不能表示

N>=8的偶数 先分解出2 2，N-=4

N>=8的奇数 先分解出2 3，N-=5