扩展欧几里得a*y-b*y=1

其实本来对数论好害怕的==测试成绩还好，虽说是因为这个点卡住了，活生生从第一掉到第五，也算差强人意

http://acm.hust.edu.cn/vjudge/contest/view.action?cid=79840#problem/E

Description

The modular modular multiplicative inverse of an integer <var>a</var> modulo <var> m</var> is an integer <var>x</var> such that <var>a^-1</var>≡<var>x</var> (mod <var>m</var>). This is equivalent to <var>a</var><var>x</var>≡1 (mod <var>m</var>).

Input

There are multiple test cases. The first line of input is an integer <var>T</var> ≈ 2000 indicating the number of test cases.

Each test case contains two integers 0 < <var>a</var> ≤ 1000 and 0 < <var>m</var> ≤ 1000.

Output

For each test case, output the smallest positive <var>x</var>. If such <var>x</var> doesn't exist, output "Not Exist".

Sample Input

Sample Output

4
Not Exist
8

后来提交发现不是错在模板改错了== 是x=0时的特判当解出x=0时是必然b*y=-1 那么b=1 a最小取1就一定存在一个y与之对应

改

#include <iostream>
#include<cstdio>
using namespace std;
int a,b,c,q,x,y;
int t;
int gcd(int a,int b)
{
     return b?gcd(b,a%b):a;
}
void extend_Euclid(int a,int b)
{
     if(b==0)
     {
          x=1;
          y=0;
          return;
     }
     extend_Euclid(b,a%b);
     int tmp=-x;
     x=-y;
     y=tmp-(a/b)*y;
}
int main()
{
     //freopen("cin.txt","r",stdin);
    while(~scanf("%d",&t))
{
     while(t--)
    {
        scanf("%d%d",&a,&b);
        
        q=gcd(a,b);

        if(q!=1)
       {
           puts("Not Exist");
           continue;
       }

       //b=-b;
        extend_Euclid(a,b);
        //printf("%I64d %I64d\n",x,y);
        x=(x%b+b)%b;
        //y=(a*x-1)/b;
        if(x==0) x=1;
        printf("%d\n",x);
}

    }




    return 0;
}

没改模板的

#include <iostream>
#include<cstdio>
using namespace std;
int a,b,c,q,x,y;
int t;
int gcd(int a,int b)
{
     return b?gcd(b,a%b):a;
}
void extend_Euclid(int a,int b)
{
     if(b==0)
     {
          x=1;
          y=0;
          return;
     }
     extend_Euclid(b,a%b);
     int tmp=x;
     x=y;
     y=tmp-(a/b)*y;
}
int main()
{
     //freopen("cin.txt","r",stdin);
    while(~scanf("%d",&t))
{
     while(t--)
    {
        scanf("%d%d",&a,&b);
        
        q=gcd(a,b);

        if(q!=1)
       {
           puts("Not Exist");
           continue;
       }

       //b=-b;
        extend_Euclid(a,b);
        //printf("%I64d %I64d\n",x,y);
        x=(x%b+b)%b;
        //y=(a*x-1)/b;
        if(x==0) x=1;
        printf("%d\n",x);
}

    }




    return 0;
}

最难以接受的是居然把b直接带进去就行了==学长说要是求最小的y就先变号然后一样。。。。