Wu_while的博客

struct matrix{ int n,m; int a[MAXN][MAXN]; matrix(int x,int y) { n=x; m=y; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) a[i][j]=0; } int *operator[](int i) { return a[i]; } void init() { for(int i=1;i<=n;i++) a[i][i]=

前置知识数论基本概念裴蜀定理在学习exgcd之前，我们需要先学习一下裴蜀定理。裴蜀定理有两条：对于任意的整数 a,ba,ba,b，存在一组整数 x,yx,yx,y，使得 ax+by=gcd(a,b)ax+by=gcd(a,b)ax+by=gcd(a,b)若 a,ba,ba,b 是整数，那么对于任意的整数 x,yx,yx,y，都有 gcd(a,b)∣ax+bygcd(a,b)|ax+bygcd(a,b)∣ax+by第一条比第二条难证，我们先来证明第一条，下面是证明过程，我尽量讲的通俗易懂：

概念什么是向量？这就是向量。从图上可以看出，向量是一条带箭头的线，准确来说，向量是一条有向线段。那么向量有什么样的意义呢？在数学中，它可以简化运算，将复杂的几何问题转化为简单的向量运算。那它又有怎样的实际意义呢？它可以表示物理中的矢量，可以表示位移、速度、力等物理量，同时可以以向量运算代替物理量运算，达到简化的目的。性质向量既然是一条有向线段，决定向量的因素有哪些呢？向量的方向向量的长度注意，没有向量的位置！也就是说，向量与它的位置无关！图中，红色的向量与蓝色的向量完全相等

一、快速幂是什么使用一般方法来计算xnx^nxn需要计算nnn次，而快速幂就是一种只需要计算log2(n)log_2(n)log2​(n)次就可以计算出xnx^nxn的算法。二、原理1.nanb=na+bn^an^b=n^{a+b}nanb=na+b(容易得很，是八年级数学内容吧)2.二进制：假设n=(10)10n=(10)_{10}n=(10)10​，那么n=(1010)2=23+21n=(1010)_{2}=2^3+2^1n=(1010)2​=23+21,所以x10=x23×x21x^{10}=