洛谷 P1082 同余方程（exgcd）

题目传送门

解题思路：

因为推导过程过于复杂，懒得写，所以题解传送门

AC代码：

 #include<iostream>

 #include<cstdio>

 using namespace std;

 long long a,b,x,y;

 void exgcd(long long p,long long o) {

     if(o == ) {

         x = ;

         y = ;

         return ;

     }

     exgcd(o,p % o);

     long long tx = x;

     x = y;

     y = tx - p / o * y;

 }

 int main() {

     cin >> a >> b;

     exgcd(a,b);

     x = (x % b + b) % b;

     printf("%lld",x);

     return ;

 }

//NOIP提高2012 Day2 T1