线性同余方程刷题小记T1:同余方程T2:青蛙的约会

90 阅读 0 评论 60 点赞

我是靠谱客的博主爱笑长颈鹿，这篇文章主要介绍线性同余方程刷题小记T1:同余方程T2:青蛙的约会，现在分享给大家，希望可以做个参考。

线性同余方程刷题小记

T1:同余方程
T2:青蛙的约会

T1:同余方程

题目链接： P1082 [NOIP2012 提高组] 同余方程
题目分析： 这个貌似比板子题都要简单一些，所以我们可以用简化一点的方法。 $a x \equiv 1 (m o d b)$ 的解即为 $a x + b y = 1$ 的 $x$ 的解，根据题目中说的一定有解，而 $g c d (a, b) ∣ 1$ 时才有解，所以 $g c d (a, b)$ 为1, $a$ , $b$ 互质,所以直接拓展欧几里得算出一组特解，然后 $x_0%b+b)%b$ 即为答案
Code:

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include<bits/stdc++.h>
using namespace std;
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 xx=x;
 x=y;
 y=xx-a/b*y;
 return r;
}
int main(){
 scanf("%d%d",&A,&B);
 exgcd(A,B,X,Y);
 X=(X%B+B)%B;
 printf("%d",X);
 return 0;
}

总结与反思:
学会从题目中找到这个题的数据的特点，从而简化算法

T2:青蛙的约会

题目： P1516 青蛙的约会
题目分析: 根据题意，不难将本题转化为一个数学方程式，即 $x + m t \equiv y + n t (m o d L)$ ,( $t$ 为时间),进一步转化可得出 $(m - n) t + k L = y - x$ ,即为一个线性不定方程，这里要特别注意 $m - n$ 要大于零，否则将两只青蛙的属性要颠倒一下。
Code:

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include<bits/stdc++.h>
using namespace std;
long long X,Y,M,N,L,XX,YY,Ans,XXX,YYY;
long long exgcd(long long a,long long b,long long &x,long long &y){
 if(b==0){
  x=1;y=0;
  return a;
 }
 long long r=exgcd(b,a%b,x,y);
 long long tem=x;
 x=y;
 y=tem-a/b*y;
 return r;
}
long long equation(long long a,long long b,long long c,long long &x,long long &y){
 long long d=exgcd(a,b,x,y);
 if(c%d) return 0;
 long long k=c/d;
 x=x*k;
 y=y*k;
 long long ans=x,s=b/d;
 ans=(ans%s+s)%s;
 return ans;
}
int main(){
 scanf("%lld%lld%lld%lld%lld",&X,&Y,&M,&N,&L);
 if(M<N){
  swap(M,N);
  swap(X,Y);
 }
 Ans=equation(M-N,L,Y-X,XXX,YYY);
 if(Ans==0) printf("Impossible");
 else printf("%lld",Ans);
 return 0;
}