数论问题

本次我们就先讲讲同余和欧几里得算法及其拓展

1、同余

同余的关键就在这个余字上面，如果m是整数，a，b是整数。
（a-b）/m为整数，则称a和b关于模m同余。记作a=b(modm)，也就是a%m=b%m,这就叫同余。
讲同余我们必不可以忽略最大公约数和最小公倍数最大公约数记作gcd，最小公倍数记作lcm，两者的关系为lcd(a,b)gcd(a,b)=ab。

2、欧几里得算法

欧几里得算法又叫做辗转相除法，其核心代码为gcs(a,b)=gcd(b,a%b);其思想转化为代码如下：

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

考虑扩展欧几里得算法一：如果gcd(a,b)存在，必有整数x，y，存在gcd(a,b)=ax+by;其思想如下：
ax1 + by1 = gcd(a,b)
b*x2 + （a mod b)*y2 = gcd(b,a mod b);
上式转化;x1=y2,y1=x2-(a/b)*y2;
转化为代码则是：

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

例题：
链接: hdu 1576.
我的代码：

#include<stdio.h>
int x,y;
int exgcd(int a,int b,int &x,int &y)
{
	if(b==0){
		x=1;
		y=0;
		return 0;
	}
	exgcd(b,a%b,x,y);
	int t=x;
	x=y;
	y=t-(a/b)*y;
} 
int main()
{
	int k,m=9973,n,b;
	scanf("%d",&k);
	while(k--){
		scanf("%d %d",&n,&b);
		exgcd(b,m,x,y);
		x=(x%m+m)%m;
		printf("%d\n",(x*n)%m);
	}
	return 0;
}

这里有一个点就是x=(x%m+m)%m;
m为gcd中的b;
其余看前面的思维公式就可以简单得出，还有一个点就是一定要在纸上得出gcd(a,b)=ax+yb这个公式。

2、欧几里得算法拓展二：
ax=b(mod n)对于未知数x有解，当且仅当gcd(a,n)|b,当方程有解时，解的个数为gcd(a,n)。其核心等式为ax=b(mod n)等价于ax+ny=b;
题目
链接: poj1061.
我的代码：

#include<iostream>
using namespace std;
int x,y,q;
int exgcd(int a,int b)
{
	if(b==0){
		x=1;
		y=0;
		q=a;
	} 
	else{
		exgcd(b,a%b);
		int t=x;
		x=y;
		y=t-(a/b)*y;
	}
}
int main()
{
	int X,Y,M,N,L;
	cin>>X>>Y>>M>>N>>L;
	int t;
	exgcd(N-M,L);
	if((X-Y)%q==0){
		int t=L/q;
		cout<<((X-Y)/q*x%t+t)%t<<endl;
	}
	else{
		cout<<"Impossible"<<endl;
	} 
}

注意事项和思维想法与拓展一差不多，自己推导会更有意思！！
本期就到这里了，下期再见。