Problem A: 求逆元
Time Limit: 1 Sec Memory Limit: 2 MB
SUBMIT: 232 Solved: 77
Description
给定正整数x,y，求最小的正整数z使得x*z mod y = 1。
Input
多组数据，每行两个整数x,y 空格隔开。2 <= x, y < 10^6。
Output
输出所求的数，如果小于y的数中不存在这样的数，输出No。
Sample Input
2 3
6 11
Sample Output
2
2
HINT
思路：原方程x*z mod y = 1可转移为：x*z-y*b=1，明显的扩展欧几里德，直接套模板。
#include<stdio.h> int exgcd(int a,int b,int &x,int &y) { int i,j; if(b==0) { x=1; y=0; return a; } i=exgcd(b,a%b,x,y); j=x; x=y; y=j-a/b*y; return i; } int main() { int a,b,x,y,r; while(scanf("%d %d",&a,&b)!=EOF) { r=exgcd(a,b,x,y); if(r==1) { while(x<0) { x+=b; y-=a; } printf("%d\n",x); } else printf("No\n"); } return 0; }
