首页 > 代码库 > HDU 1576 (乘法逆元)
HDU 1576 (乘法逆元)
题目链接: http://acm.hdu.edu.cn/showproblem.php?pid=1576
题目大意：求(A/B）mod 9973。但是给出的A是mod形式n，n=A%9973。
解题思路：
两种思路，一种从乘法逆元角度，另一种从扩展GCD推公式角度。
①乘法逆元：
先来看下逆元和乘法逆元的关系，对于A*X=B，有X=A-1*B,A-1就是普通的逆元了，在这里就是倒数。
如果A*X=B mod n，变成同余式了，那么A-1依然是存在的，只不过不是倒数了，一般把同余之后的逆元称为乘法逆元。（ - -。好像这个定义是错的）。
题目如果是(A/B) mod 9973, 那就简单了。关键A同余化了，所以B也要同余化，这时候就有把B逆运算（除变乘)，从普通变成同余状态的乘法逆元运算mod_reverse(B，9973)。
这样A的同余状态a=n，B的同余状态b=mod_reverse(B，9973)。
那么题目直接转化成（a*b）mod 9973 了。
#include "cstdio"#define LL long longLL ex_gcd(LL a,LL b,LL &x,LL &y){ if(a==0&&b==0) return -1; if(b==0) {x=1;y=0;return a;} LL d=ex_gcd(b,a%b,y,x); y-=a/b*x; return d;}LL mod_reverse(LL a,LL n){ LL x,y,d=ex_gcd(a,n,x,y); if(d==1) return (x%n+n)%n; else return -1;}int main(){ LL T,n,B; scanf("%I64d",&T); while(T--) { scanf("%I64d%I64d",&n,&B); LL x=mod_reverse(B,9973); printf("%I64d\n",(n*x)%9973); }}
②扩展GCD角度：
设A=9973*y+n，因为A%B=0，所以(9973*y+n)=B*x，其中x=A/B
移项，有B*x+9973*(-y)=n。
联想到扩展GCD的式子：B*X+9973*Y=1，两边都乘以n，B*(nX)+9973*(nY)=n。
这样x=nX，y=-nY，只要求出X和Y就行了，套扩展GCD模板即可。
注意这里扩展GCD求出的一组x和y可能都是负值，如果x%9973是错的，对负数取模的方法是(x%mod+mod)%mod.
#include "cstdio"#define LL long longLL ex_gcd(LL a,LL b,LL &x,LL &y){ if(a==0&&b==0) return -1; if(b==0) {x=1;y=0;return a;} LL d=ex_gcd(b,a%b,y,x); y-=a/b*x; return d;}int main(){ LL T,n,B; scanf("%I64d",&T); while(T--) { scanf("%I64d%I64d",&n,&B); LL x,y; ex_gcd(B,9973,x,y); x*=n; printf("%I64d\n",(x%9973+9973)%9973); }}
| 12168956 | 2014-11-13 00:56:37 | Accepted | 1576 | 0MS | 228K | 519B | C++ | Physcal |
HDU 1576 (乘法逆元)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。