HDU1576 (A/B)[乘法逆元，拓展欧几里得]

发表于 | 更新于 | | 阅读次数：

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1576

求出B的乘法逆元，用A乘该逆元再对9973取模即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <cstdio>
#include <cstring>
using namespace std;
typedef long long ll;
void exgcd(ll a, ll b, ll& d, ll& x, ll& y) {
	if(!b) { d=a; x=1; y=0; }
	else { exgcd(b,a%b,d,y,x); y-=x*(a/b); }
}
ll inv(ll a, ll n) {
	ll d,x,y;
	exgcd(a,n,d,x,y);
	return d==1 ? (x+n)%n : -1;
}

ll A,B;
int main() {
	int T;
	scanf("%d",&T);
	while(T--) {
		scanf("%lld%lld",&A,&B);
		if(A==0) {
			printf("0\n");
			continue;
		}
		ll ans=(A*inv(B,9973))%9973;
		printf("%lld\n",ans);
	}
}