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
#include<cstdio>
#include<cstring>
#include<iostream>
#include<cmath>
#include<map>
#include<algorithm>
using namespace std;
typedef long long ll;
ll extended_gcd(ll a,ll b,ll &x,ll &y)
{
    if(!a&&!b)return -1;
    if(!b){x=1;y=0;return a;}
    ll d=extended_gcd(b,a%b,y,x);
    y-=a/b*x;
    return d;
}
ll m[1005],a[1005];
bool solve(ll &m0,ll &a0,ll m,ll a)
{
    ll x,y;
    ll g=extended_gcd(m0,m,x,y);
    if(abs(a-a0)%g)return false;
    x*=(a-a0)/g;
    x%=m/g;
    a0=(x*m0+a0);
    m0*=m/g;
    a0%=m0;
    if(a0<0)a0+=m0;
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX