更相减损术
概念
《九章算术》是中国古代的数学专著，其中的“更相减损术”可以用来求两个数的最大公约数。
原文： 可半者半之，不可半者，副置分母、子之数，以少减多，更相减损，求其等也。以等数约之。
白话文： （如果需要对分数进行约分，那么）可以折半的话，就折半（也就是用2来约分）。如果不可以折半的话，那么就比较分母和分子的大小，用大数减去小数，互相减来减去，一直到减数与差相等为止，用这个相等的数字来约分。
使用步骤
第一步：任意给定两个正整数；判断它们是否都是偶数。若是，则用2约简；若不是则执行第二步。
第二步：以较大的数减较小的数，接着把所得的差与较小的数比较，并以大数减小数。继续这个操作，直到所得的减数和差相等为止。 则第一步中约掉的若干个2与第二步中等数的乘积就是所求的最大公约数。 求“等数”的办法就是“更相减损术”。
代码
#include<bits/stdc++.h>
using namespace std;
int ans=1;
void gxjss(int x,int y) {
while(x != y) {
if(x > y) x -= y;
else y -= x;
}
ans *= x;
printf("gcd=%d\n", ans);
}
int main() {
int m,n;
scanf("%d %d",&m, &n);
while(m % 2 == 0 && n % 2 == 0) {
m /= 2, n /= 2;
}
gxjss(m, n);
return 0;
}
更相减损术 与 辗转相除法
辗转相除法也可以用来求两个数的最大公约数。
更相减损术和辗转相除法的主要区别在于前者所使用的运算是“减”，后者是“除”。
从算法思想上看，两者并没有本质上的区别，但是在计算过程中，如果遇到一个数很大，另一个数比较小的情况，可能要进行很多次减法才能达到一次除法的效果，从而使得算法的时间复杂度退化为O(N)，其中N是原先的两个数中较大的一个。
相比之下，辗转相除法的时间复杂度稳定于O(logN)。
拉姆齐定理
友谊(friend)定理
在至少6人中，或者有3人，他们互相认识；或者有3人，他们两两互相不认识。
证明如下：
从任意一点(此处以N1为示范)可以引5条线，由鸽巢(抽屉)原理可知，至少有3条边会同色假设为红色(蓝色类似，如图一)，考虑此三边的终点(N3/N4/N5)的着色情况，将此三点中的任意两点连线着红色，即可构成一个红色的K3，若此三点都着蓝色，则可构成一个蓝色K3(如图二)，得证！
对于给定的两个整数m,n≥2,则一定存在一个最小整数r,使得用两种颜色(例如红蓝)无论给Kr的每条边如何染色，总能找到一个红色的Km或者蓝色的Kn。显然，当p>=r的时候，Kp也满足这个性质。r可以看做一个有关m,n的二元函数，即r(m,n)。
在友谊定理中r(3,3)=6。
基本性质：
①等价性 r(m,n)=r(n,m)
②r(2,n)=n k2较特殊 只有一条边 最小的kr为Kn
③r(m,2)=m 由上面两条可得
好的好的，到现在，今天的内容就全部结束了 *★,°*:.☆(￣▽￣)/$:*.°★*
（都散了吧散了吧）
咳咳
矩阵
概念
在数学中，矩阵(Matrix)是一个按照长方阵列排列的实数或复数集合，最早来自于方程组的系数及常数所构成的方阵。 矩阵是高等代数学中的常见工具，也常见于统计分析等应用数学学科中，矩阵的运算是数值分析领域的重要问题。在物理学中，矩阵在电路学、力学、光学和量子物理中都有应用。在计算机学科中，三维动画制作也需要用到矩阵。 由m×n个数aij排成的m行n列的数表称为m行n列的矩阵，简称m×n矩阵。记作：
这m×n个数称为矩阵A的元素，简称元。数aij位于矩阵A的第i行第j列，称为矩阵A的(i,j)元，以数aij为(i,j)元的矩阵可记为(aij)或(aij)m×n，m×n矩阵A也记作Amn。
元素是实数的矩阵称为实矩阵，元素是复数的矩阵称为复矩阵。而行数与列数都等于n的矩阵称为n阶矩阵或n阶方阵。n阶方阵中所有i=j的元素aij组成的斜线称为(主)对角线，所有i+j=n+1的元素aij组成的斜线称为辅对角线。
矩阵的基本运算
矩阵的基本运算包括加法、减法、数乘、转置、共轭和共轭转置等。
1、加法与减法
对于两个同型(行列数一样)矩阵A和B，加法就是把对应(i,j)元做加法运算。 例如：
矩阵的加法运算满足结合律和交换律，即：
A+B=B+A
(A+B)+C=A+(B+C)
矩阵的减法与加法运算类似，例如：
2、数乘
矩阵的数乘是指一个数乘以一个矩阵，只要把这个数乘到每一个(i,j)元上。
例如：
矩阵的数乘运算满足结合律和分配率，即：
(λμ)A=λ(μA)
(λ+μ)A=λA+μA
λ(A+B)=λA+λB
矩阵的加法、减法和数乘运算合称为矩阵的“线性”运算。
3、转置
把矩阵A的行换成同序数的列所得到的新矩阵称为A的转置矩阵，这一过程称为矩阵的转置。
例如：
矩阵的转置运算满足以下运算律：
4、共轭
对于复矩阵，其共轭矩阵定义为：(A)i,j=Ai,j。例如，一个2×2的复矩阵共轭如下：
5、共轭转置
矩阵的共轭转置定义为： (A*)i,j=Aj,i ，也可以写成：A*=(A)T=AT ,例如一个2×2的复矩阵共轭转置如下：
★ 矩阵的行列式
一个n×n的方阵A的行列式记为det(A)或者|A|，一个2×2矩阵的行列式可表示如下：
把一个n阶行列式中的元素aij所在的第i行和第j列划去后，留下来的n-1阶行列式叫做元素aij的余子式，记作Mij。记Aij=(-1)i+j Mij，叫做元素aij的代数余子式。例如：
A23=(-1)2+3M23=-M23
一个n×n矩阵的行列式等于其任意行(或列)的元素与对应的代数余子式乘积之和，即：
★矩阵的乘法运算
两个矩阵乘法仅当第一个矩阵A的列数和第二个矩阵B的行数相等时才能定义(做乘法)。
如A是m*n矩阵，B是n*p矩阵，它们的乘积C是一个m*p矩阵C=(cij)，它的任意一个元素值为
ci,j = ai,1 + ai,2b2,j + … + ai,nbn,j =
并将此乘积记为：C=AB，例如：
矩阵的乘法运算满足结合律，左分配律，右分配律，但是不满足交换律。即：
先上个板题 矩阵 A×B
两种写法
写法一：
#include <bits/stdc++.h>
using namespace std;
int a[105][105],b[105][105],c[105][105];
int main () {
int n,m,p;
scanf("%d %d",&n,&m);
for(int i=1;i<=n;i++) {
for(int j=1;j<=m;j++) {
scanf("%d",&a[i][j]);
}
}
scanf("%d",&p);
for(int i=1;i<=m;i++) {
for(int j=1;j<=p;j++) {
scanf("%d",&b[i][j]);
}
}
for(int i=1;i<=n;i++) {
for(int j=1;j<=p;j++) {
for(int k=1;k<=m;k++) {
c[i][j]+=a[i][k]*b[k][j];
}
}
}
for(int i=1;i<=n;i++) {
for(int j=1;j<=p;j++) {
printf("%d ",c[i][j]);
}
printf("\n");
}
return 0;
}写法二 ：
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int MAXN = 105;
struct Matrix {
int n, m;
LL mp[MAXN][MAXN];
Matrix() { memset(mp, 0, sizeof mp); }
void read() {
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++) scanf("%lld", &mp[i][j]);
}
void print() {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) printf("%lld ", mp[i][j]);
printf("\n");
}
}
Matrix operator*(const Matrix &x) const {
Matrix ans;
ans.n = n;
ans.m = x.m;
for (int i = 1; i <= ans.n; i++)
for (int j = 1; j <= ans.m; j++)
for (int k = 1; k <= m; k++) ans.mp[i][j] += mp[i][k] * x.mp[k][j];
return ans;
}
};
int main() {
Matrix A, B, C;
scanf("%d %d", &A.n, &A.m);
B.n = A.m;
A.read();
scanf("%d", &B.m);
B.read();
C = A * B;
C.print();
return 0;
}
这真的清爽整洁吗
经典模型
Fibonacci 第 n 项
借助 这篇博客 理解更佳，这里不再赘述
const int mod = 1000000007;
struct Matrix {
int a[3][3];
Matrix() { memset(a, 0, sizeof a); } // 构造函数，矩阵初始化全零
Matrix operator*(const Matrix &b) const {
Matrix res;
for (int i = 1; i <= 2; ++i)
for (int j = 1; j <= 2; ++j)
for (int k = 1; k <= 2; ++k)
res.a[i][j] = (res.a[i][j] + a[i][k] * b.a[k][j]) % mod;
return res;
}
} ans, base;
void init() { // 初始化 ans、base 矩阵
base.a[1][1] = base.a[1][2] = base.a[2][1] = 1;
ans.a[1][1] = ans.a[1][2] = 1;
}
void qpow(int b) { // 求
while (b) {
if (b & 1) ans = ans * base;
base = base * base;
b >>= 1;
}
}
int main() {
int n = read();
if (n <= 2) return puts("1"), 0;
init();
qpow(n - 2);
println(ans.a[1][1] % mod);
}标签：运算,int,杂谈,矩阵,转置,数学,aij,Matrix From： https://www.cnblogs.com/pangtuan666/p/16758076.html