拓展欧几里得算法 $\quad O(n \ast log(a+m))$

拓展欧几里得算法
解题思路:利用拓展欧几里得算法求解
将求解$a_i∗x_i≡b_i(mod \quad m_i)$问题转换为拓展欧几里得问题,$a_i∗x_i≡b_i(mod \quad m_i) \Rightarrow \quad a_i∗x_i+m*y≡b_i(mod \quad m_i)$
一.解的分析
当$b_i为(a_i,m)的倍数时,方程有解,因为a_i\*x_i为(a_i,m)的倍数,m\*y也为(a_i,m)的倍数,\\\\若方程有解时,b_i也必然为(a_i,m)的倍数,\\\\若方程无解,那么b_i必然不是(a_i,m)的倍数\\\\拓展欧几里得算法是求解a_i∗x_i+m\*y≡(a,m)问题的,\\\\若有解时,和a_i∗x_i≡b_i相差的只是一个倍数\frac{b_i}{(a_i,m)},最后x乘上\frac{b_i}{(a_i,m)}就是最后答案$

$ O(n \ast log(a+m))$

#include<cstdio>

using namespace std;
int exgcd(int a,int b,int& x,int& y)
{
    if(!b)
    {
        x=1,y=0;
        return a;
    }
    int t = exgcd(b,a%b,y,x);
    y-=a/b*x;
    return t;
}
int main()
{
    int n;
    scanf("%d",&n);
    while(n--)
    {
        int a,b,m,x,y;
        scanf("%d%d%d",&a,&b,&m);
        int res = exgcd(a,m,x,y);
        if(b%res) printf("impossible\n");
        else printf("%d\n",b/res*((long long)x+m)%m);
    }
    return 0;
}

$\color{brown}{喜欢题解的话,欢迎点赞、收藏、关注(三连)喔,如有什么疑问,欢迎评论下方指出}$