蓝桥杯数论知识点大纲:
-
欧几里得算法求最大公约数(gcd),最小公倍数(lcm)
-
算数基本定理: $N=x_1^{a_1}+x_2^{a_2}+x_3^{a_3}+\cdots+x_n^{a_n}$
-
约数个数:$(a_1+1)(a_2+1)\cdots(a_n+1)$
-
约数之和:$(1+p_1^{1}+p_1^{2}+\cdots+p_1^{n})(1+p_2^{1}+p_2^{2}+\cdots+p_2^{n})\cdots(1+p_3^{1}+p_3^{2}+\cdots+p_3^{n}) $
-
拓展欧几里得算法:
$$gcd(a,b) = ax_1+by_1$$
$$gcd(b,a\%b)= bx_{2}+(a\%b)y_2$$
$$ ax_1+by_1=bx_2+(a-a/b\times b)y_2 $$
$$ x_1=y_2, y_1=x_2-a/b\times y_2$$
于是,我们可以用类似于树形dp的方法,先递归到$x=1,y=0$ ,然后从$y_2,x_2$倒推$x_1,y_1$
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, y, x); //向下一层问询x1,y1
y -= (a / b) * x; //用当前层的x2,y2求上一层的x1,y1
return d;
}