标签：www https int DAY1 QBXT bmatrix problem 集训 gcd

$Day 1$

$ASCII$

简单来说，$ASCII$ 其实就是字符与数字之间的映射

比如说，$'a'$ 的 $ASCII$ 就是 $97$

模运算：%

来复习一下小学数学：$a/b=c……d$
这里的$d$ 就是 $a$ 除以 $b$ 的余数，在计算机中，用%来表示
通过这个式子，我们进而得出 $a=b*c+d$

请一定要记住这个式子

我们知道 $5$ % $3 = 2$
那 $(-5)$ % $3$ 等于多少呢
还有 $5$ % $(-3)$ 、$(-5)$ % $(-3)$呢
通过计算机的计算，我们知道 $(-5)$ % $3 = -2$ ， $5$ % $(-3) = 2$ ，$(-5)$ % $(-3) = -2$

于是我们发现，$a$ % $b$ 的符号是由 $a$ 决定的，与 $a$ 的符号一致
而且，$a$ % $b$ 的数值是由 $|a| - |b|$ 决定的

下面将是一个很重要的公式：

$(a+b)$ % $c = (a$ % $c+b$ % $c)$ % $c$

为什么？

设 $a = k*c+a'$，$b=q*b+b'$
所以 $(a+b)$ % $c = (k*c+q*c+a'+b')$ % $c$
显然，上面的式子就可以转化为 $(a'+b')$ % $c$
最后，原式 $=(a$ % $c+b$ % $c)$ % $c$

同理，

$(a-b)$ % $c = (a$ % $c-b$ % $c)$ % $c$
$(a*b)$ % $c = (a$ % $c*b$ % $c)$ % $c$

那除法行不行呢？

通过验证，不行！

来看几道例题：

计算$(a_1+a_2+a_3+...+a_n)\bmod p$
很自然会想到这样写

int ans=0;
for (int i=1;i<=n;i++)
	ans = ans+a[i];
cout << ans%p << endl;

可是你怎么就知道ans不会炸int？

所以就需要边加边模

int ans=0;
for (int i=1;i<=n;i++)
	ans = (ans+a[i])%p;//0~p-1
cout << ans << endl;

计算$(a_1-a_2+a_3-a_4+a_5....)\bmod p$

ans=0;
for (int i=1;i<=n;i++)
	if (i%2==1) ans=(ans+a[i])%p;
	else ans=((ans-a[i])%p+p)%p;//0~p-1
cout << ans << endl;

计算$a_1*a_2*a_3*...*a_n\bmod p$

这里要把ans转成long long，就需要用$1ll$去乘ans

ans=1;
for (int i=1;i<=n;i++)
	ans=1ll*ans*a[i]%p;
cout << ans << endl;

$gcd( Greatest$ $Common$ $Divisor )$

$gcd(a,b)$是指找到一个最大的$c$，使得$a\bmod c=0$且$b\bmod c=0$

当然，$STL$中提供了一个__$ gcd $的函数，但是不建议用

如何求$gcd$呢？

下面介绍辗转相除法（欧几里得算法）

$gcd(a,b)=gcd(b,a\bmod b)$

怎样实现？

可以用递归实现
当$b=0$时，$gcd$的值一定时$a$

int gcd(int a,int b){
	if (b==0) return a;
	return gcd(b,a%b);
}

顺便讲一下$lcm（Least$ $Common$ $Multiple）$
$lcm(a,b)$是指找到一个最小的$c(c>0)$，使得$c\bmod a=0$，且$c\bmod b=0$

当然$gcd$和$lcm$是有公式的

$lcm(a,b)=\frac{a*b}{gcd(a,b)}$

int lcm(int a,int b){
	return a*b/gcd(a,b);
}

为了防止爆$int$，可以这么写：

int lcm(int a,int b){
	return a/gcd(a,b)*b;
}

快速幂

求$(x^y)\bmod p$的值

先来讲一下$c++$中一些数学函数

$sqrt(x)$ 计算$\sqrt x$
$floor(x)$ 向下取整
$ceil(x)$ 向上取整
$round(x)$ 四舍五入
$pow(x,y)$ 计算$x^y$

关于这个$pow$，如果$y$的值是分数，其结果就是$x$的$y$次方根

那么这道题可以用$pow$吗？

不能！

好，咱们假设要求$x^{37}$
我们可以将其转化为$(x^{18})^2*x$
而$(x^{18})$可以化为$(x^9)^2$
$(x^9)^2=(x^4)^2*x$
$(x^4)=(x^2)^2$
$x^2=(x)^2$
于是，我们就将原本需要计算$37$次转化为只需计算$7$次！

这就是快速幂

int ksm(int a,int b,int p){
	if (b==0) return 1%p;
	int c=ksm(a,b/2,p);
	c=1ll*c*c%p;
	if (b%2==1) c=1ll*c*a%p;
	return c; 
} 

int main(){
	int x,y,p,ans=1;
	cin >> x >> y >> p;
	for (int i=1;i<=y;i++)//O(y)
		ans=1ll*ans*x%p;
	cout << ans << endl;
}

矩阵（二维数组）

加法

两个矩阵的对应位置相加（前提是两个矩阵大小要一致）！

例如

$\begin{bmatrix}1 & 2 \\ 3 & 4 \end{bmatrix} + \begin{bmatrix}2 & 3 \\ 3 & 3 \end{bmatrix}= \begin{bmatrix}3 & 5 \\ 6 & 7 \end{bmatrix} $

减法

两个矩阵的对应位置相减（前提是两个矩阵大小要一致）！

例如

$\begin{bmatrix}1 & 2 \\ 3 & 4 \end{bmatrix}- \begin{bmatrix}2 & 3 \\ 3 & 3 \end{bmatrix}= \begin{bmatrix}-1 & -1 \\ 0 & 1 \end{bmatrix}$

乘法

矩阵$A$的列数应和矩阵$B$的行数一致
他们相乘的结果$C$的行数等于$A$的行数，列数等于$B$的列数
$C$的第$i$行第$j$列的数等于$A$的$i$行$B$的$j$列对应相乘，然后相加；

例如

$\begin{bmatrix}1 & 2 \\ 3 & 4 \end{bmatrix} * \begin{bmatrix}2 & 2 & 3 \\ 2 & 3 & 3 \end{bmatrix}= \begin{bmatrix}6 & 8 & 9 \\ 14 & 18 & 21 \end{bmatrix} $

#include<iostream>
#include<cstring>

using namespace std;

struct matrix
{
	int n,m;//矩阵的行数和列数
	int a[10][10];//a[i][j]代表当前矩阵第i行第j列的数是多少 
	matrix()//构造函数 函数名和结构体名一模一样 每次新创建一个matrix变量 就会调用一次 
	{
		n=m=0;
		memset(a,0,sizeof(a));
	}
};
matrix operator*(const matrix &a,const matrix &b)//返回a*b的结果 
//c++没有定义过的运算才能重载
//n^3 n<=200 
{
	matrix c;
	c.n = a.n;
	c.m = b.m;
	for (int i=1;i<=c.n;i++)
		for (int j=1;j<=c.m;j++)
			for (int k=1;k<=a.m;k++)
				c.a[i][j] = (c.a[i][j] + a.a[i][k] * b.a[k][j]);
	return c;
} 

int main()
{
	matrix a,b,c;
	//f(a,b);
	c=a*b;
    return 0;
}

斐波那契额数列

求斐波那契数列第$n$项$\bmod p$的值 $(n\le 10^9)$

枚举当然是不行的，而且通项公式也不行（了解一下$f_n = (\frac { \sqrt 5 +1 }{2})^2 - (\frac { \sqrt 2 -1 }{2})^2$）

可以用矩阵来做

$\begin{bmatrix}f_i & f_{i-1} \end{bmatrix} * \begin{bmatrix}1 & 1\\ 1 & 0 \end{bmatrix}= \begin{bmatrix}f_i+f_{i-1} & f_{i} \end{bmatrix}= \begin{bmatrix}f_{i+1} & f_{i} \end{bmatrix} $

于是我们知道
每次乘这个矩阵，$i$的值都会向后推进$1$

难道我们要乘$n$遍这个矩阵吗？

显然不行

注意，我们小学学过的乘法结合律在矩阵中也是适用的
所以我们可以先求此矩阵的$n$次方
怎么求呢？
快速幂啊！

#include<iostream>
#include<cstring>

using namespace std;

int n,p;

struct matrix
{
	int n,m;//矩阵的行数和列数
	int a[5][5];//a[i][j]代表当前矩阵第i行第j列的数是多少 
	matrix()//构造函数 函数名和结构体名一模一样 每次新创建一个matrix变量 就会调用一次 
	{
		n=m=0;
		memset(a,0,sizeof(a));
	}
}m1,m2,m3;
matrix operator*(const matrix &a,const matrix &b)//返回a*b的结果 
{
	matrix c;
	c.n = a.n;
	c.m = b.m;
	for (int i=1;i<=c.n;i++)
		for (int j=1;j<=c.m;j++)
			for (int k=1;k<=a.m;k++)
				c.a[i][j] = (c.a[i][j] + 1ll * a.a[i][k] * b.a[k][j])%p;
	return c;
} 

matrix ksm(matrix a,int b)//计算a^b
{
	if (b==1) return a;
	matrix c=ksm(a,b/2);//计算c=a^(b/2)
	c=c*c;
	if (b%2==1) c=c*a;//当b是奇数时 需要额外再乘一个a
	return c; 
} 

int main()
{
	cin >> n >> p;
	m1.n=1;m1.m=2;
	m1.a[1][1]=1;m1.a[1][2]=0;//m1=[f1, f0]
	m2.n=m2.m=2;
	m2.a[1][1]=1;m2.a[1][2]=1;
	m2.a[2][1]=1;m2.a[2][2]=0;
	//m2 = [ 1, 1
	//       1 ,0 ]
	m3 = m1 * ksm(m2,n);//m3=[fn+1,fn]
	cout << m3.a[1][2] << endl;
    return 0;
}

初等数论

请你不要被名字吓到，它不过是围绕质数展开的

所谓质数，就是只有$1$和它本身两个因子的数

怎样判断质数？
很简单嘛，根据定义来判断就行了

bool is_prime(int n){
	if (n<2) return false;
	for (int i=2;i*i<=n;i++)
	//for (int i=2;i<=n/i;i++)
		if (n%i==0) return false;
	return true;
}

接下来就很玄学了

费马小定理

若$p$为质数，且$gcd(a,p)=1$，那么$a^{p-1}\bmod p=1$

由此，我们转化一下
$x\div a\bmod p = x* {\frac {1}{a}}\bmod p=x*a^{p-2}\bmod p$

所以，当$p$是质数时，$\div a$就等于$*a^{p-2}$
这就是乘法逆元

当然实现需要用快速幂

如果$p$不是质数呢？

欧拉定理

对于任意模数$p$，保证$gcd(a,p)=1$，那么$a^{\varphi (p)}\equiv 1\pmod p$

这个$\varphi (p)$指的是$1~n$中有多少个数与$n$互质

由上面的公式，我们进而得出
$a^{\varphi (p)-1}\equiv {\frac{1}{a}}\pmod p$

int phi(int n){
	int ans = 0;
	for(int i = 1;i <= n;i++){//O(n log n)
		if(gcd(i, n) == 1){
			ans++;
		}
	}
	return ans;
}

$\varphi (p)$怎么求呢？

int phi(int n){
	int ans = n;
	for(int i = 2;i <= n;i++){//O(n)
		if(n % i == 0){//i一定是质因子 
			ans = ans / i * (i - 1);//ans = ans * (1 - 1 / i)
			while(n % i == 0){
				n/=i;//找到就全部干掉（出掉） ，在没有这个质因子 
			}
		}
	}
	return ans;
}

优化？

int phi(int n){
	int ans = n;
	for(int i = 2;i * i <= n;i++){//O(sqrt(n))
		if(n % i == 0){//i一定是质因子 
			ans = ans / i * (i - 1);//ans = ans * (1 - 1 / i)
			while(n % i == 0){
				n/=i;//找到就全部干掉（出掉） ，在没有这个质因子 
			}
		}
	}
	if(n != 1){
		ans = ans / n * (n - 1);
	}
	return ans;
}

$exgcd$（扩展欧几里得算法）

由于本人才疏学浅，此区域没太明白，姑且放上zhx老师的代码和OIWIKI的链接

int exgcd(int a,int b,int &x,int &y)
//要求gcd(a,b)
//还要求 x * a + y * b = gcd(a,b)
//函数的返回值为gcd(a,b)
//而x,y的值 通过 取地址 返回
{
	if (b==0)
	{
		x=1;y=0;
		return a;
	}
	int g,xp,yp;
	g=exgcd(b,a%b,xp,yp);
	//一定有 xp * b + yp * (a%b) = g
	x=yp;
	y=xp-a/b*yp;
	return g; 
}

不懂看这里

$crt(Chinese Remainder Theorem)$中国剩余定理

同上

#include<iostream>
#include<algorithm>

using namespace std;

#define ll long long

int n;

ll a[100010],p[100010];

ll gcd(ll a,ll b)
{
	if (b==0) return a;
	else return gcd(b,a%b);
}

void hebing(ll p1,ll a1,ll p2,ll a2,ll &p,ll &a)
//给定方程
//x%p1=a1
//x%p2=a2
//想要合并两个方程为
//x%p=a
{
	if (p1<p2) swap(p1,p2),swap(a1,a2);
	p=p1/gcd(p1,p2)*p2;//p=lcm(p1,p2);
	a=a1;
	while (a%p2!=a2)//O(min(p1,p2))
		a+=p1; 
} 

int main()
{
	cin >> n;
	for (int i=1;i<=n;i++)
	{
		cin >> p[i] >> a[i];
		a[i] %= p[i];
	}
	ll p_=1,a_=0;//定义初始方程为x%1=0
	for (int i=1;i<=n;i++)
		hebing(p_,a_,p[i],a[i],p_,a_);
	cout << a_ << endl; 
}

不懂看这里

https://noip.ac/rs/show_problem/3292
https://www.luogu.com.cn/problem/CF1617B
https://noip.ac/rs/show_problem/3293
https://www.luogu.com.cn/problem/B3619
https://www.luogu.com.cn/problem/B3620
https://www.luogu.com.cn/problem/P1143
https://noip.ac/rs/show_problem/2161
https://www.luogu.com.cn/problem/P1226
https://www.luogu.com.cn/problem/P3390
https://noip.ac/rs/show_problem/889
https://www.luogu.com.cn/problem/P1939

标签：www,https,int,DAY1,QBXT,bmatrix,problem,集训,gcd
From： https://www.cnblogs.com/TianJiajun-chaqjs/p/18170571

QBXT五一集训DAY1笔记

\(Day 1\)

\(ASCII\)

模运算：%

\(gcd( Greatest\) \(Common\) \(Divisor )\)

快速幂

矩阵（二维数组）

初等数论

\(exgcd\)（扩展欧几里得算法）

\(crt(Chinese Remainder Theorem)\)中国剩余定理

相关文章

赞助商

阅读排行