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 <algorithm>
using namespace std;
int n;
long long int m,r;
long long int x,y,c;
long long int gcd(long long int a1,long long int b1)
{
    while(b1 != 0)
    {
        long long int tmp = b1;
        b1 = a1 % b1;
        a1 = tmp;
    }
    return a1;
}
void extendgcd(long long int a1, long long int b1)
{
    if (b1 == 0)
    {
        x = 1;
        y = 0;  
        return;
    }
    extendgcd(b1, a1%b1);
    long long int tmp = y;
    y = x - a1/b1 * y;
    x = tmp;
}
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX