HDU——1576 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%9973，也就是n ，要求求出(A/B)%9973。

题解：因为(A/B)%9973为除法取模，不能直接取模，需要转换成求逆元的问题，(A/B)%9973=(A%9973*B的逆元%9973)%9973

下面用两种方法求逆元，上代码：

扩展欧几里得：

#include <iostream>
#include <vector>
using namespace std;
int gcd(int a, int b,int &x,int &y){//扩展欧几里得求逆元模板
	if(b==0){
		x=1,y=0;
		return a;
	}
	int q=gcd(b,a%b,y,x);
	y-=a/b*x;
	return q;
}
int main(){
	int t;
	cin >> t;
	while(t--){
		int n,b,x,y;
		cin >> n >> b;
		gcd(b,9973,x,y);//求b的逆元
		int ans=(x%9973*n+9973)%9973;//x为b的逆元
        //加9973 是为了防止ans为负数  也可以这样写：
        /*
        int ans=(x%9973*n)%9973;
        if(ans<0) ans+=9973;
        */
		cout << ans << endl;
	}
	return 0;
} 

费马小定理：（因为gcd(B,9973) = 1，所以B的逆元为b的（9973-2）次方）这是费马小定理的应用，而且9973必须为素数，也就是模的那个数为素数。而扩展欧几里得对此没有要求。

#include <iostream>
using namespace std;
int quick(int a,int b,int c){//快速幂模板
	int ans=1;
	a=a%c;
	while(b){
		if(b&1) ans=(ans*a)%c;
		b>>=1;
		a=(a*a)%c;
	}
	return ans;
}
int main(){
	int t;
	cin >> t;
	while(t--){
		int n,b;
		cin >> n >> b;
		int ans=(n*quick(b,9971,9973)%9973+9973)%9973;//b的逆元为b的（9973-2）次方，这是费马小定理的应用
        //第二种写法同上，解释同上
		cout << ans << endl;
	}
}