ZOJ Problem Set – 3609
Modular InverseTime Limit:2 Seconds Memory Limit:65536 KB
The modular modular multiplicative inverse of an integeramodulomis an integerxsuch thata-1≡x(modm). This is equivalent toax≡1 (modm).
Input
There are multiple test cases. The first line of input is an integerT≈ 2000 indicating the number of test cases.
Each test case contains two integers 0 <a≤ 1000 and 0 <m≤ 1000.
Output
For each test case, output the smallest positivex. If suchxdoesn’t exist, output "Not Exist".
Sample Input33 114 125 13Sample Output4Not Exist8ReferencesAuthor:WU, ZejunContest:The 9th Zhejiang Provincial Collegiate Programming Contest
首先我来回顾下欧几里德的几个定理，有助于理解这道题； 定理一：如果d = gcd(a, b)，则必能找到正的或负的整数k和l，使 d = a*x+ b*y。 定理二：若gcd(a, b) = 1，则方程ax ≡ c (mod b)在[0, b-1]上有唯一解。 定理三：若gcd(a, b) = d，则方程ax ≡ c (mod b)在[0, b/d – 1]上有唯一解。
转载请注明出处：寻找&星空の孩子
题目链接：?problemId=4712
对于ax+by=1; 即ax=1（mod b） 当且仅当gcd（a,b）!=1 的时候，无解！
#include<stdio.h>void exgcd(int a,int b,int &d,int &x,int &y){if(!b){d=a;x=1;y=0;}else{exgcd(b,a%b,d,y,x);y-=x*(a/b);}}int main(){int T,a,m;scanf("%d",&T);while(T–){int d,x,y;scanf("%d%d",&a,&m);exgcd(a,m,d,x,y);if(d==1){while(x<=0){x+=m/d;}printf("%d\n",x);}elseprintf("Not Exist\n");}return 0;}
，行动是治愈恐惧的良药，而犹豫、拖延将不断滋养恐惧。
