扩展欧几里得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
3 3 11 4 12 5 13
Sample Output
4 Not Exist 8
改
#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;
}
