终于开了数论课了，，再也不是只贴模板了，稍微懂了点原理，先来一发链接
（里面的最后一题是孙子定理，也是模板题）
---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
先贴几个最常见的模板：
最大公约数（辗转相除法）
#define ll long long
ll gcd(ll a,ll b){
return b?gcd(b,a%b):a;
}扩展欧几里得：求ax+by=gcd(a,b)中的x，y，其中d=gcd（a，b）
#define ll long long
ll exgcd(ll a,ll b,ll &x,ll &y){
ll d;
if (b==0){
x=1;y=0;return a;
}
d=exgcd(b,a%b,y,x);
y-=a/b*x;
return d;
}孙子定理的模板：
其中a[]是各个除数，m[]是各个余数，n是同余式子的个数，学完同余再来解释模板原理
ll CRT(ll a[],ll m[],ll n){
ll M=1,d,ret=0,i,x,y,Mi,temp;
for(i=0;i<n;i++) M*=m[i];
for(i=0;i<n;i++){
Mi=M/m[i];
d=Exgcd(m[i],Mi,x,y);
temp=mod_mul(y,Mi,M);
temp=mod_mul(temp,a[i],M);
ret=(ret+temp)%M;
}
return (M+ret)%M;
}扩展欧几里得的最经典应用：
解决一次不定方程ax+by=c
（1）ax+by=c有解的充分必要条件是（a，b）=c
（2）利用公式的x0，y0得出一组特解，然后所有解为x=x0+b*k/gcd(a,b) y=y0-a*k/gcd(a,b)
（3）题中有时候是求出x或者y的最小正整数解，利用通式取余即可
下面是各个题的代码：
A：
ll x,y,n,m,l;
ll a,b,g,mul;
int main(){
//input;
while(scanf("%lld%lld%lld%lld%lld",&x,&y,&m,&n,&l)!=EOF){
g=exgcd(m-n,-1*l,a,b);
if ((y-x)%g){
puts("Impossible");
continue;
}
a*=(y-x)/g;
mul=-1*l/g;
//printf("%lld %lld\n",a,mul);
a=(a%mul+mul)%mul;
printf("%lld\n",a);
}
return 0;
}
B：
int main(){
//input;
int i,j,k;
pow2[0]=1;
for(i=1;i<=35;i++) pow2[i]=2LL*pow2[i-1];
//for(i=1;i<=35;i++) printf("%lld\n",pow2[i]);
while(scanf("%lld%lld%lld%d",&a,&b,&c,&k)!=EOF){
if (k==0) break;
if (a==b){
puts("0");
continue;
}
g=exgcd(c,pow2[k],x,y);
if ((b-a)%g){
puts("FOREVER");
continue;
}
//printf("%lld\n",g);
x*=(b-a)/g;
l=pow2[k]/g;
//printf("%lld %lld\n",x,l);
x=(x%l+l)%l;
printf("%lld\n",x);
//cout<<endl;
}
return 0;
}C：范围很小，直接根据题意for循环暴力即可
D：
ll a,b,g;
ll l,r;
ll x,y;
int main(){
//input;
while(scanf("%I64d%I64d",&a,&b)!=EOF){
g=exgcd(a,b,x,y);
if (g!=1){
puts("sorry");
continue;
}
x=(x%b+b)%b;
y=(1-a*x)/b;
printf("%I64d %I64d\n",x,y);
}
return 0;
}
E：
ll x,y,n,m,l;
ll a,b,g,mul;
int main(){
//input;
while(scanf("%lld%lld%lld%lld%lld",&x,&y,&m,&n,&l)!=EOF){
g=exgcd(m-n,l,a,b);
if ((y-x)%g){
puts("Pat");
continue;
}
a*=(y-x)/g;
mul=-1*l/g;
if (mul<0) mul=-1*mul;
//printf("%lld %lld\n",a,mul);
a=(a%mul+mul)%mul;
printf("%lld\n",a);
}
return 0;
}F：
int main(){
//input;
while(scanf("%I64d%I64d%I64d",&a,&b,&m)!=EOF){
if (a+b+m==0) break;
tot=ansx=ansy=INF;
tot*=99999999;
g=exgcd(a,-1*b,x,y);
x*=m/g;
y*=m/g;
l=b/g;if (l<0) l=-1*l;
r=a/g;if (r<0) r=-1*r;
x1=(x%l+l)%l;
y=(y%r+r)%r;
x2=(m+b*y)/a;
for(x=x1;x<=x2;x+=l){
y=(a*x-m)/b;
if (y<0) continue;
if (x+y<=ansx+ansy&&tot>=x*a+b*y){
ansx=x;
ansy=y;
tot=x*a+b*y;
}
}
g=exgcd(a,b,x,y);
x*=m/g;
y*=m/g;
l=b/g;if (l<0) l=-1*l;
r=a/g;if (r<0) r=-1*r;
x1=(x%l+l)%l;
y=(y%r+r)%r;
x2=(m+b*y)/a;
for(x=x1;x<=x2;x+=l){
y=(m-a*x)/b;
if (y<0) continue;
if (x+y<=ansx+ansy&&tot>=x*a+b*y){
ansx=x;
ansy=y;
tot=x*a+b*y;
}
}
m=-1*m;
g=exgcd(a,-1*b,x,y);
x*=m/g;
y*=m/g;
l=b/g;if (l<0) l=-1*l;
r=a/g;if (r<0) r=-1*r;
x1=(x%l+l)%l;
y=(y%r+r)%r;
x2=(m+b*y)/a;
for(x=x1;x<=x2;x+=l){
y=(a*x-m)/b;
if (y<0) continue;
if (x+y<=ansx+ansy&&tot>=x*a+b*y){
ansx=x;
ansy=y;
tot=x*a+b*y;
}
}
printf("%I64d %I64d\n",ansx,ansy);
}
return 0;
}G：孙子定理模板应用没什么好说的。。。。
-------------------------------------------------------------------------------------------------------------------------------------------------------------------
来几篇好的欧几里得的原理介绍的博客：
http://www.cnblogs.com/frog112111/archive/2012/08/19/2646012.html
http://www.acmerblog.com/extend-gcd-5610.html
看完这几个，刷完这几个题，模板弄下来，就基本没什么问题了。。这是最基本的内容了，学了同余等知识之后会有更多的结论
京公网安备 11010502036488号