hdu1576 A/B（欧几里德扩展和逆元）

要求(A/B)%9973，但由于A很大，我们只给出n(n=A%9973)(我们给定的A必能被B整除，且gcd(B,9973) = 1)。

Input

数据的第一行是一个T，表示有T组数据。 
每组数据有两个数n(0 <= n < 9973)和B(1 <= B <= 10^9)。

Output

对应每组数据输出(A/B)%9973。

Sample Input

2
1000 53
87 123456789

Sample Output

7922
6060

首先了解一下同余定理：

（a*b)%c=(a%c*b%c)%c

(a+b)%c=(a%c+b%c)%c

证明

a = k1*m+r1
b = k2*m+r2
(a+b)%m=(( k1*m+r1 )+( k2*m+r2 ))%m
= (( k1+k2 )*m+( r1+r2 ))% m
= (r1+r2 )%m
= (a%m+b%m)% m
(a+b)%m = (a%m+b%m)%m

解题思路：a/b对9973取余等价于（a×（b的逆元））%9973，等价于(a%9973*(b的逆元%9973))%9973,即（n*(b的逆元%9973））,但是n可能也很大，有可能wa，再用一次同余定理得：（n%9973×（（b的逆元%9973）%9973））%9973.

AC代码如下：

#include<stdio.h>
#include<algorithm>
#include<math.h>
#include<iostream>
#include<map>
#define mod 9973
#include<vector>
#include<set>
#include<string>
#include<string.h>
using namespace std;
typedef long long ll;
ll exgcd(ll a,ll b,ll &x,ll &y)
{
	if(b==0)
	{
		x=1;
		y=0;
		return a;
	}
	ll r=exgcd(b,a%b,x,y);
	ll t=y;
	y=x-(a/b)*y;
	x=t;
	return r;
}
ll iva(ll a)   //求逆元 
{
	ll x,y;
	exgcd(a,mod,x,y);
	return (x+mod)%mod;
}
char num[mod];
int main()
{
	ll n,t,b;
	scanf("%d",&n);
	while(n--)
	{
		scanf("%d%d",&t,&b);
		printf("%d\n",((t%mod*iva(b)%mod)%mod));
	}
	return 0;
}