基础数论--例题

题目链接：https://www.acwing.com/problem/content/206/

推导过程：

存疑处也就是不知如何从在求出x*a+y*b=m同余方程的一个解的情况下求出x和y的通解。

补充：假设求的x=x1,y=y1

　　那么ax1+by1=m

　　　　ax1+by1+kab-kab=m(k为整数)

　　　　(x1+kb)a+(y1+ka)b=m

　　　　所以讲道理代码里边将t换成a2也是能够过的

　　　　但是ax1+by1+kab/gcd(a,b)-kab/gcd(a,b)=m能够保证kab/gcd(a.b)是整除

　　　　所以(x1+kb/gcd(a,b))a+(y1+ka/gcd(a,b))b=m成立

　　　　所以通解俩都行。

启发自https://www.cnblogs.com/mogeko/p/10587343.html

代码：

 1 #include<iostream>
 2 using namespace std;
 3 typedef long long LL;
 4 LL exgcd(LL a,LL b,LL& x,LL& y){
 5     if(b==0){
 6         x=1,y=0;
 7         return a;
 8     }else{
 9         LL d=exgcd(b,a%b,y,x);
10         y=y-a/b*x;
11         return d;
12     }
13 }
14 int main(void){
15     int n;
16     cin>>n;
17     LL a1,m1;
18     cin>>a1>>m1;
19     bool flag=true;
20     for(int i=0;i<n-1;i++){
21         LL a2,m2;
22         cin>>a2>>m2;
23         LL k1,k2;
24         LL d=exgcd(a1,a2,k1,k2);
25         if((m2-m1)%d){
26             flag=false;
27             break;
28         }else{
29             k1*=(m2-m1)/d;
30             LL t=a2/d;
31             k1=(k1%t+t)%t;
32             m1=a1*k1+m1;
33             a1=a1/d*a2;
34         }
35     }
36     if(flag){
37         cout<<(m1%a1+a1)%a1<<endl;
38     }else{
39         cout<<-1<<endl;
40     }
41     return 0;
42 }