A/B · znzryb

## 思路讲解

## AC代码

AC
[https://vjudge.net/solution/58198800](https://vjudge.net/solution/58198800)

```cpp
// Problem: A/B
// Contest: Virtual Judge - HDU
// URL: https://vjudge.net/problem/HDU-1576
// Memory Limit: 32 MB
// Time Limit: 1000 ms
// by znzryb
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (int i = (a); i >= (b); --i)
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define fi first
#define se second
#define pb push_back

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll> pll;
typedef array<ll,3> arr;
typedef double DB;
constexpr ll MAXN=static_cast<ll>(1e6)+10,INF=static_cast<ll>(5e18)+3,mod=9973;

ll N,B,T,A[MAXN];

void exgcd(ll a,ll b,ll &x,ll &y){
	if(b==0){	// x，y都是反的
		x=1,y=0;
	}else{
		exgcd(b,a%b,y,x);
		y-=a/b*x;	// 实际是y=x1-a/b*y1	但实际上因为我们在上面反了一下，所以这里也要反一下
	}
}
// (ax-1)%m=0
inline void solve(){
	// 其实就是要求B的逆元
	cin>>N>>B;
	ll x_,y_;
	exgcd(B,mod,x_,y_);	// x_就是B的逆元
	// (A/B)%mod = (A/B)%mod *(bk)%mod=(Ak)%mod
	ll ans=(N*x_)%mod;
	if(ans<0) ans+=mod;
	cout<< ans <<'\n';
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>T;
	while(T--){
		solve();
	}
	return 0;
}
/*
AC
https://vjudge.net/solution/58198800
*/
```

## 心路历程（WA，TLE，MLE……）