756ka网站建设,中建名城建设有限公司 网站,小程序开发平台打不了字,东莞企业网站搭建制作如果b与c互素#xff0c;则(a/b)%ca*b^((c)-1)%c其中是欧拉函数。或者(a/b)%ca*b^(c-2)%c
如果b与c不互素#xff0c;则(a/b)%c(a%bc)/b
对于b与c互素和不互素都有(a/b)%c(a%bc)/b成立
乘法逆元用扩展欧几里得定理#xff1a;
例题#xff1a;ZOJ - 3609
题干#xf…如果b与c互素则(a/b)%ca*b^((c)-1)%c其中是欧拉函数。或者(a/b)%ca*b^(c-2)%c
如果b与c不互素则(a/b)%c(a%bc)/b
对于b与c互素和不互素都有(a/b)%c(a%bc)/b成立
乘法逆元用扩展欧几里得定理
例题ZOJ - 3609
题干
The modular modular multiplicative inverse of an integer a modulo m is an integer x such that a-1≡x (mod m). This is equivalent to ax≡1 (mod m).
Input
There are multiple test cases. The first line of input is an integer T ≈ 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 positive x. If such x doesnt exist, output Not Exist.
Sample Input
3
3 11
4 12
5 13
Sample Output 4
Not Exist
8
题目大意如果存在逆元输出逆元不存在逆元输出Not Exist。
AC代码
#includebits/stdc.h
#define ll long long
using namespace std;int e_gcd(int a,int b,int x,int y) {if(b 0) {x1;y0;return a;}int qe_gcd(b,a%b,y,x);y-a/b*x;return q;
}
int main()
{long long t;int x,y,a,b;while(~scanf(%lld,t) ) {while(t--) {scanf(%d%d,a,b);int gcd e_gcd(a,b,x,y);if(gcd !1) {puts(Not Exist);continue; }if(x0) xb;printf(%d\n,x); }}return 0 ;
}注意一下是x0的时候都不算逆元需要xb来变成正数不能是非负数。
